- 冒泡排序
- 选择排序
- 插入排序
- 快速排序
- 归并排序
- 希尔排序
public static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
冒泡排序
关键点：两两比较，每一轮外层循环能得出一个最大值放最后，下一轮循环从0到n-2之间的元素对比
public static int[] bubbleSort(int[] array) {
if (array.length == 0)
return array;
for (int i = 0; i < array.length; i++)
for (int j = 0; j < array.length - 1 - i; j++)
if (array[j + 1] < array[j]) {
swap(array,j,j+1);
}
return array;
}
选择排序
关键点：第n轮外层循环 找到最小值的位置n （先确定最小的数）
public static int[] selectionSort(int[] array) {
if (array.length == 0)
return array;
for (int i = 0; i < array.length; i++) {
int minIndex = i;
for (int j = i; j < array.length; j++) {
if (array[j] < array[minIndex]) //找到最小的数
minIndex = j; //将最小数的索引保存
}
if (minIndex!=i)
swap(array,minIndex,i);
}
return array;
}
插入排序
关键点：每一次外层循环 最前面的n个数是有序的 第n次xun循环时 第n个数依次与第n-1个数对比 小于再与前面的n-2个位置元素对比 否则结束
public static int[] insertionSort(int[] array) {
if (array.length == 0)
return array;
int current;
for (int i = 1; i < array.length; i++) {
current = array[i];
int preIndex = i - 1;
while (preIndex >= 0 && current < array[preIndex]) {
array[preIndex + 1] = array[preIndex];
preIndex--;
}
array[preIndex + 1] = current;
}
return array;
}
快速排序
思路
1.首先设定一个分界值，通过该分界值将数组分成左右两部分。
2.将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。
3.然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
4.重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
public static int[] quickSort(int[] array, int start, int end) {
if (array.length < 1 || start < 0 || end >= array.length || start > end) return null;
int left = start, right = end;
//基准值
int key = array[left];
while (left < right) {
while (left < right && key <= array[right]) {
right--;
}
//找到比基准小的元素
array[left] = array[right];
while (left < right && key >= array[left]) {
left++;
}
//找到比基准大的元素
array[right] = array[left];
}
//还原基准值
array[left] = key;
//对基准值 左边的元素进行递归排序 不包括基准值
quickSort(array, start, left - 1);
//对基准值右边的元素进行递归排序 不包括基准值
quickSort(array, right + 1, end);
return array;
}
归并排序
归并排序(MERGE- SORT)是利用归并的思想实现的排序方法，该算法采用经典的分治( divide-
and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案修补”在一起，即分而治之)。
public static int[] mergeSort(int[] array) {
if (array.length < 2) return array;
int mid = array.length / 2;
int[] left = Arrays.copyOfRange(array, 0, mid);
int[] right = Arrays.copyOfRange(array, mid, array.length);
return merge(mergeSort(left), mergeSort(right));
}
public static int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
for (int index = 0, i = 0, j = 0; index < result.length; index++) {
if (i >= left.length)
result[index] = right[j++];
else if (j >= right.length)
result[index] = left[i++];
else if (left[i] > right[j])
result[index] = right[j++];
else
result[index] = left[i++];
}
return result;
}
希尔排序
