1、冒泡排序 O(n^2)
冒泡排序，记下最后一次交换的位置，如果后边没有交换则交换位置为0，必然是有序的，然后下一次排序从第一个比较到上次记录的位置结束即可，优化后代码如下：
public static void bubbleSort(Comparable[] arr) {
int end = arr.length ;
int last = 0;
for (int i = 0; i < arr.length; i++) {
last = 0;
for (int j = 1; j < end; j++) {
if (arr[j - 1].compareTo(arr[j]) < 0) {
continue;
}
SortTestHelper.swap(arr, j - 1, j);
last = j;// 记录最后一次的交换位置,在此之后的元素在下一轮扫描中均不考虑
}
if (last > 0) {
end = last;
}
}
}
2、选择排序 O(n^2)
public static void selectSort(Comparable[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
// 寻找[i, n)区间里的最小值的索引
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j].compareTo(arr[minIndex]) < 0) {
minIndex = j;
}
}
if (i == minIndex)
continue;
SortTestHelper.swap(arr, i, minIndex);
}
}
可以对选择排序进行优化，在每一轮循环中, 可以同时找到当前未处理元素的最大值和最小值
public static void selectSort(Comparable[] arr){
int left = 0, right = arr.length - 1;
while(left < right){
int minIndex = left;
int maxIndex = right;
// 在每一轮查找时, 要保证arr[minIndex] <= arr[maxIndex]
if(arr[minIndex].compareTo(arr[maxIndex]) > 0)
swap(arr, minIndex, maxIndex);
for(int i = left + 1 ; i < right; i ++)
if(arr[i].compareTo(arr[minIndex]) < 0)
minIndex = i;
else if(arr[i].compareTo(arr[maxIndex]) > 0)
maxIndex = i;
swap(arr, left, minIndex);
swap(arr, right, maxIndex);
left ++;
right --;
}
}
3、插入排序 O(n^2)
插入排序在有序的数据的情况下，可以进化成O(n) 级别的算法，相比O(n^2)性能高很多，它与选择排序的区别是，选择排序每一次是从前往后找最小小值，而插入排序是每次从后与它前一个元素进行比较，然后插入，插入排序适合数据量小，且有序的数据
public static void insertSort(Comparable[] arr) {
for (int i = 1; i < arr.length; i++) {
for (int j = i; j > 0; j--) {
if (arr[j].compareTo(arr[j - 1]) > 0) {
break;
}
SortTestHelper.swap(arr, j, j - 1);
}
}
}
4、希尔排序 O(n^2)
希尔排序是插入排序的进化版本，插入排序是每一次轮询是跟前一个元素比较，而希尔排序是每一次轮询跟前第 h 个元素比较
public static void sort(Comparable[] arr) {
int step = 3;
int n = arr.length;
int h = 0;
while (step * h < n) {
h = step * h + 1;
}
while (h > 0) {
for (int i = h; i < n; i++) {
//对 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序
for (int j = i; j >= h; j -= h) {
if (arr[j - h].compareTo(arr[j]) > 0) {
SortTestHelper.swap(arr, j - h, j);
}
}
}
h /= step;
}
}
5、归并排序 O(nlogn)
Merge Sort是一个O(nlogn)复杂度的算法，可以在1秒之内轻松处理100万数量级别的数据，
不要轻易尝试使用SelectionSort，InsertionSort或者BubbleSort处理100万级的数据，
否则你就见识了O(n^2)的算法和O(nlogn)算法的本质差异
public static void sort(Comparable[] arr) {
mergeSort(arr, 0, arr.length - 1);
}
// // 将arr[l...mid]和arr[mid+1...r]两部分进行归并
private static void mergeSort(Comparable[] arr, int left, int right) {
if (left >= right) {
return;
}
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// 对于arr[mid] <= arr[mid+1]的情况,不进行merge
// 对于近乎有序的数组非常有效,但是对于一般情况,有一定的性能损失
if (arr[mid].compareTo(arr[mid + 1]) < 0) {
return;
}
merge(arr, left, right, mid);
}
private static void merge(Comparable[] arr, int left, int right, int mid) {
if (left >= right) {
return;
}
int tempLength = right - left + 1;
Comparable[] tempArr = new Comparable[tempLength];
for (int i = left; i <= right; i++) {
tempArr[i - left] = arr[i];
}
int leftP = left;
int rightP = mid + 1;
// 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
for (int k = left; k <= right; k++) {
// 如果左半部分元素已经全部处理完毕
if (leftP > mid) {
arr[k] = tempArr[rightP - left];
rightP++;
continue;
}
// 如果右半部分元素已经全部处理完毕
if (rightP > right) {
arr[k] = tempArr[leftP - left];
leftP++;
continue;
}
// 左半部分所指元素 < 右半部分所指元素
if (tempArr[leftP - left].compareTo(tempArr[rightP - left]) < 0) {
arr[k] = tempArr[leftP - left];
leftP++;
continue;
}
// 左半部分所指元素 >= 右半部分所指元素
arr[k] = tempArr[rightP - left];
rightP++;
continue;
}
}
归并排序可以优化的几个点
1、对于近乎有序的数组，也就是arr[mid]<=arr[mid+1]的情况，不进行merge操作
2、由于归并排序以后，切割的数组越小，越趋近于有序，此时使用插入排序效率更高，可以达到O(n)级别,对于小数据规模的近乎有序的数组，可以优先使用插入排序效率更高
优化后代码如下：
// 递归使用归并排序,对arr[l...r]的范围进行排序
private static void sort(Comparable[] arr, int l, int r) {
// 对于小规模数组, 使用插入排序
if( r - l <= 15 ){
InsertionSort.sort(arr, l, r);
return;
}
int mid = (l+r)/2;
sort(arr, l, mid);
sort(arr, mid + 1, r);
// 对于arr[mid] <= arr[mid+1]的情况,不进行merge
// 对于近乎有序的数组非常有效,但是对于一般情况,有一定的性能损失
if( arr[mid].compareTo(arr[mid+1]) > 0 )
merge(arr, l, mid, r);
}
归并排序还有一种写法是“自底向顶” 归并
//自顶向上归并排序
private static void mergeButtomToUp(Comparable[] arr) {
int n = arr.length;
//step 从 1,2,4,8....
for (int step = 1; step < n; step = 2 * step) {
for (int i = 0; i + step < n; i += 2 * step) {
int right = Math.min(n - 1, 2 * step + i - 1);
int mid = i + step - 1;
if (arr[mid + 1].compareTo(arr[mid]) >= 0)
continue;
merge(arr, i, right, mid);
}
}
}
与快速排序一样，归并排序也是分而治之的应用。不同的是，它先让左右两部分进行排序，然后把它们合并起来。
在排序左右两部分时，同样使用归并排序。归并排序需要额外的存储空间，
这部分空间和被排序的数组所占空间一样大，每次递归调用中分配空间，这样会使性能下降。但是归并排序平方的平衡度比
快速排序要好很多。每次都能平分n/2的平衡度，而快速排序最坏的情况下分成1/n.
网友评论