几种常用排序算法

2020/06/07 20:02

冒泡排序

private static void bubbleSort(int[] array) {
int temp;
int endNum = array.length - 1;
for (int i = 0; i < endNum; i++) {
for (int j = 0; j < (endNum) - i; j++) {
if (array[j] > array[j + 1]) {
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}


快速排序

private static void quickSort(int[] array, int start, int end) {
if (start < end) {
int base = array[start];
int temp;
int i = start;
int j = end;

do {
while (array[i] < base && i < end) {
i++;
}
while (array[j] > base && j > start) {
j--;
}
if (i <= j) {
temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
} while (i <= j);

if (start < j) {
quickSort(array, start, j);
}
if (end > i) {
quickSort(array, i, end);
}
}
}


选择排序

    private static void selectSort(int[] array) {
int temp, length = array.length;
for (int i = 0; i < length; i++) {
int k = i;
for (int j = length - 1; j > i; j--) {
if (array[j] < array[k]) {
k = j;
}
}
temp = array[k];
array[k] = array[i];
array[i] = temp;
}
}


插入排序

private static void insertSelect(int[] array) {
int length = array.length, temp, j;
for (int i = 1; i < length; i++) {
temp = array[i];
for (j = i; j > 0 && temp < array[j - 1]; j--) {
array[j] = array[j - 1];
}
array[j] = temp;
}
}


归并排序

private static void mergeSort(int[] array, int left, int right) {
int t = 1;// 每组元素个数
int size = right - left + 1;
while (t < size) {
int s = t;// 本次循环每组元素个数
t = 2 * s;
int i = left;
while (i + (t - 1) < size) {
merge(array, i, i + (s - 1), i + (t - 1));
i += t;
}
if (i + (s - 1) < right)
merge(array, i, i + (s - 1), right);
}
}

/**
* 归并算法实现
*
* @param array
* @param low 低位
* @param mid 中位
* @param high 高位
*/
private static void merge(int[] array, int low, int mid, int high) {
int i = low;
int j = mid + 1;
int k = 0;
int[] tmpArray = new int[high - low + 1];

while (i <= mid && j <= high) {
if (array[i] <= array[j]) {
tmpArray[k] = array[i];
i++;
} else {
tmpArray[k] = array[j];
j++;
}
k++;
}

while (i <= mid) {
tmpArray[k] = array[i];
i++;
k++;
}
while (j <= high) {
tmpArray[k] = array[j];
j++;
k++;
}

for (k = 0, i = low; i <= high; i++, k++) {
array[i] = tmpArray[k];
}
}


希尔排序

public static void shellSort(int[] array) {
int increment = 12;
do {
increment = increment / 3 + 1;
shellPass(array, increment);

} while (increment > 1);
}

private static void shellPass(int[] array, int d) {
for (int i = d; i < array.length; i++) {
int temp = array[i];
int j = i - d;
while (j >= 0 && array[j] > temp) {
array[j + d] = array[j];
j -= d;
}
array[j + d] = temp;
}
}


0 评论
0 收藏
0