talk is simple, show me your code！！先上代码,之后补全注释(个人学习向，有问题欢迎交流)
快速排序
private static void quickSort(int[] array, int l, int r) {
if (array == null) {
return;
} else if (array.length == 0) {
return;
} else {
if (l < r) {
int i = quickSortArray(array, l, r);
quickSort(array, l, i - 1);
quickSort(array, i + 1, r);
}
}
}
private static int quickSortArray(int[] array, int l, int r) {
if (array == null || l < 0 || r < 0 || l > r) {
return 0;
} else {
int x = l;
int y = r;
int temp = array[l];
while (x < y) {
while (x < y && array[y] >= temp) {
y--;
}
if (x < y) {
array[x] = array[y];
}
while (x < y && array[x] < temp) {
x++;
}
if (x < y) {
array[y] = array[x];
}
}
array[x] = temp;
return x;
}
}
冒泡排序
private static void bubbleSort(int[] array) {
if (array == null) {
return;
} else if (array.length == 1) {
return;
} else {
boolean flag = true;
int i = 1;
while (flag) {
flag = false;
for (int j = 0; j < array.length - i; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
flag = true;
}
}
i++;
}
}
}
插入排序
/**
* 第i次排的时候认为前i-1项已经排序完成，把新的这个数插入到前i-1项中的正确位置即可
*
* @param array
*/
private static void insertSort(int[] array) {
if (array == null) {
return;
} else if (array.length == 1) {
return;
} else {
int i, j;
for (i = 1; i < array.length; i++) {
for (j = i - 1; j >= 0 && array[j] > array[j + 1]; j--) {
// swap(array[j], array[j + 1]);
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
选择排序
/**
* 每次选最小的放到最前面
*
* @param array
*/
private static void selectSort(int[] array) {
if (array == null) {
return;
} else if (array.length == 1) {
return;
} else {
int i, j;
int index = 0;
for (i = 0; i < array.length; i++) {
index = i;
for (j = i; j < array.length; j++) {
if (array[j] < array[index]) {
index = j;
}
}
int temp = array[i];
array[i] = array[index];
array[index] = temp;
}
}
}
堆排序
public static void heapSort(int[] array) {
/**
* 构建大顶堆
*/
for (int i = array.length / 2 - 1; i >= 0; i--) {
adjustHeap(array, i, array.length);
}
/**
* 调整堆，第一项与最后一项互换，然后对前length-2项重新构建大顶堆
*/
for (int i = array.length - 1; i > 0; i--) {
// swap(array[0], array[i]);
int temp = array[0];
array[0] = array[i];
array[i] = temp;
adjustHeap(array, 0, i);
}
}
/**
* 调整大顶堆,头尾元素互换，然后重新构建大顶堆
* @param array
* @param i
* @param length
*/
private static void adjustHeap(int[] array, int i, int length) {
int temp = array[i];
for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
if (array[k + 1] > array[k] && k + 1 < length) {
k++;
}
if (array[k] > temp) {
array[i] = array[k];
i = k;
} else {
break;
}
}
array[i] = temp;
}
归并排序
/**
* 归并排序
* @param array
* @param first
* @param last
* @param temp
*/
private static void mergeSort(int array[], int first, int last, int temp[]) {
if (array == null) {
return;
}
if (first < last) {
int mid = (first + last) / 2;
mergeSort(array, first, mid, temp);
mergeSort(array, mid + 1, last, temp);
mergeArray(array, first, mid, last, temp);
}
}
/**
* 将两个排好序的序列合并
* @param array
* @param first
* @param mid
* @param last
* @param temp
*/
private static void mergeArray(int[] array, int first, int mid, int last, int[] temp) {
int l = first;
int r = mid;
int x = mid + 1;
int y = last;
int k = 0;
while (l <= r && x <= y) {
if (array[l] <= array[x]) {
temp[k++] = array[l++];
} else {
temp[k++] = array[x++];
}
}
while (l <= r) {
temp[k++] = array[l++];
}
while (x <= y) {
temp[k++] = array[x++];
}
for (int i = 0; i < k; i++) {
array[first + i] = temp[i];
}
}
希尔排序
/**
* 希尔排序，对直接插入排序的改进，又叫缩小增量排序
*
* @param array
* @param length
*/
private static void shellSort(int[] array, int length) {
int temp = 0;
int j = 0;
/**
* 调整步长，假如数组长度为10，那么步长的变化就是5-2-1
*/
for (int increment = length / 2; increment > 0; increment = increment / 2) {
for (int i = increment; i < length; i++) {
temp = array[i];
for (j = i - increment; j >= 0; j -= increment) {
if (array[j] > temp) {
array[j + increment] = array[j];
} else {
break;
}
}
array[j + increment] = temp;
}
}
}
交换值
private static void swap(int i, int j) {
if (i == j) {
return;
}
i ^= j;
j ^= i;
i ^= j;
}
网友评论