目录

一.所用到的工具类二.选择排序三.插入排序四.归并排序1.基础归并排序(递归)2.归并排序的优化点3.自底向上的归并排序(迭代)4.归并的应用 五.快速排序1.单路快速排序2.随机化快速排序3.双路快速排序4.三路快速排序 六.堆排序七.算法的性能测试

一.所用到的工具类

测试的数据：

生成一个随机的数组 下面函数有两个功能： rangeL和rangeR的值的差距越大，则生成随机性非常大的数据，很少有重复数据 rangeL和rangeR的值的差很小，则生成很多重复的数据

// 生成有n个元素的随机数组,每个元素的随机范围为[rangeL, rangeR] public static Integer[] generateRandomArray(int n, int rangeL, int rangeR) { assert rangeL <= rangeR; Integer[] arr = new Integer[n]; for (int i = 0; i < n; i++) arr[i] = new Integer((int)(Math.random() * (rangeR - rangeL + 1) + rangeL)); return arr; }

生成一个近乎有序的数组：

// 生成一个近乎有序的数组 // 首先生成一个含有[0...n-1]的完全有序数组, 之后随机交换swapTimes对数据 // swapTimes定义了数组的无序程度: // swapTimes == 0 时, 数组完全有序 // swapTimes 越大, 数组越趋向于无序 public static Integer[] generateNearlyOrderedArray(int n, int swapTimes){ Integer[] arr = new Integer[n]; for( int i = 0 ; i < n ; i ++ ) arr[i] = new Integer(i); for( int i = 0 ; i < swapTimes ; i ++ ){ int a = (int)(Math.random() * n); int b = (int)(Math.random() * n); int t = arr[a]; arr[a] = arr[b]; arr[b] = t; } return arr; }

用于检测排序后是否真的有序了，可用一个assert语句进行判断：

public static boolean isSorted(Comparable[] arr){ for( int i = 0 ; i < arr.length - 1 ; i ++ ) if( arr[i].compareTo(arr[i+1]) > 0 ) return false; return true; }

用于测试排序时间的函数：

public static void testSort(String sortClassName, Comparable[] arr){ // 通过Java的反射机制，通过排序的类名，运行排序函数 try{ // 通过sortClassName获得排序函数的Class对象 Class sortClass = Class.forName(sortClassName); // 通过排序函数的Class对象获得排序方法 Method sortMethod = sortClass.getMethod("sort",new Class[]{Comparable[].class}); // 排序参数只有一个，是可比较数组arr Object[] params = new Object[]{arr}; long startTime = System.currentTimeMillis(); // 调用排序函数 sortMethod.invoke(null,params); long endTime = System.currentTimeMillis(); assert isSorted( arr ); System.out.println( sortClass.getSimpleName()+ " : " + (endTime-startTime) + "ms" ); } catch(Exception e){ e.printStackTrace(); } }

二.选择排序

public static void sort(Comparable[] arr){ int n = arr.length; for( int i = 0 ; i < n ; i ++ ){ // 寻找[i, n)区间里的最小值的索引 int minIndex = i; for( int j = i + 1 ; j < n ; j ++ ) // 使用compareTo方法比较两个Comparable对象的大小 if( arr[j].compareTo( arr[minIndex] ) < 0 ) minIndex = j; swap( arr , i , minIndex); } } private static void swap(Object[] arr, int i, int j) { Object t = arr[i]; arr[i] = arr[j]; arr[j] = t; }

三.插入排序

public static void sort(Comparable[] arr){ int n = arr.length; for (int i = 0; i < n; i++) { // 寻找元素arr[i]合适的插入位置 // 写法1 // for( int j = i ; j > 0 ; j -- ) // if( arr[j].compareTo( arr[j-1] ) < 0 ) // swap( arr, j , j-1 ); // else // break; // 写法2 // for( int j = i; j > 0 && arr[j].compareTo(arr[j-1]) < 0 ; j--) // swap(arr, j, j-1); // 写法3,优化后 Comparable e = arr[i]; int j = i; for( ; j > 0 && arr[j-1].compareTo(e) > 0 ; j--) arr[j] = arr[j-1]; arr[j] = e; } }

四.归并排序

1.基础归并排序(递归)

需要开辟一个新数组，复制原数组的数据，新数组左右两部分分别下标 i 和 j ，不断地选小的数复制到原数组上，左右两部分则可以归并成一个有序的数组。

// 将arr[l...mid]和arr[mid+1...r]两部分进行归并 private static void merge(Comparable[] arr, int l, int mid, int r) { Comparable[] aux = Arrays.copyOfRange(arr, l, r+1); // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1 int i = l, j = mid+1; for( int k = l ; k <= r; k ++ ){ if( i > mid ){ // 如果左半部分元素已经全部处理完毕 arr[k] = aux[j-l]; j ++; } else if( j > r ){ // 如果右半部分元素已经全部处理完毕 arr[k] = aux[i-l]; i ++; } else if( aux[i-l].compareTo(aux[j-l]) < 0 ){ // 左半部分所指元素 < 右半部分所指元素 arr[k] = aux[i-l]; i ++; } else{ // 左半部分所指元素 >= 右半部分所指元素 arr[k] = aux[j-l]; j ++; } } } // 递归使用归并排序,对arr[l...r]的范围进行排序 private static void sort(Comparable[] arr, int l, int r) { if (l >= r) return; int mid = (l+r)/2; sort(arr, l, mid); sort(arr, mid + 1, r); merge(arr, l, mid, r); } public static void sort(Comparable[] arr){ int n = arr.length; sort(arr, 0, n-1); }

2.归并排序的优化点

1.尽管合并排序最坏情况运行时间为O(nlgn)，插入排序的最坏运行时间为O(n^2)，但是插入排序的常数因子使得它在n较小时，运行要更快一些。因此，在合并排序算法中，当子问题足够小时，采用插入排序就比较合适了。 2.需要归并的两个有序数组，如果左边的最大值比右边的最小值还小，则不进行merge。

private static void sort(Comparable[] arr, int l, int r) { // 优化2: 对于小规模数组, 使用插入排序 if( r - l <= 15 ){ InsertionSort.sort(arr, l, r); return; } int mid = (l+r)/2; sort(arr, l, mid); sort(arr, mid + 1, r); // 优化1: 对于arr[mid] <= arr[mid+1]的情况,不进行merge // 对于近乎有序的数组非常有效,但是对于一般情况,有一定的性能损失 if( arr[mid].compareTo(arr[mid+1]) > 0 ) merge(arr, l, mid, r); }

3.自底向上的归并排序(迭代)

public static void sort(Comparable[] arr){ int n = arr.length; // Merge Sort Bottom Up 无优化版本 // for (int sz = 1; sz < n; sz *= 2) // for (int i = 0; i < n - sz; i += sz+sz) // // 对 arr[i...i+sz-1] 和 arr[i+sz...i+2*sz-1] 进行归并 // merge(arr, i, i+sz-1, Math.min(i+sz+sz-1,n-1)); // Merge Sort Bottom Up 优化 // 对于小数组, 使用插入排序优化 for( int i = 0 ; i < n ; i += 16 ) InsertionSort.sort(arr, i, Math.min(i+15, n-1) ); for( int sz = 16; sz < n ; sz += sz ) for( int i = 0 ; i < n - sz ; i += sz+sz ) // 对于arr[mid] <= arr[mid+1]的情况,不进行merge if( arr[i+sz-1].compareTo(arr[i+sz]) > 0 ) merge(arr, i, i+sz-1, Math.min(i+sz+sz-1,n-1) ); }

4.归并的应用

归并可以用来求数组的逆序对数

比较6和5的时候，5比6小，则会有两个逆序对，6和5，8和5，累加器加2。然后5的光标移到7上。6比7小，6的光标移到8上，比较8和7，则会产生一个逆序对，累加器加1。

五.快速排序

1.单路快速排序

// 对arr[l...r]部分进行partition操作 // 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p] private static int partition(Comparable[] arr, int l, int r){ Comparable v = arr[l]; int j = l; // arr[l+1...j] < v ; arr[j+1...i) > v for( int i = l + 1 ; i <= r ; i ++ ) if( arr[i].compareTo(v) < 0 ){ j ++; swap(arr, j, i); } swap(arr, l, j); return j; } // 递归使用快速排序,对arr[l...r]的范围进行排序 private static void sort(Comparable[] arr, int l, int r){ if( l >= r ) return; int p = partition(arr, l, r); sort(arr, l, p-1 ); sort(arr, p+1, r); } public static void sort(Comparable[] arr){ int n = arr.length; sort(arr, 0, n-1); }

不足：当数据接近有序，会退化到O(n2) 解决办法：随机化数组的p值。

2.随机化快速排序

private static int partition(Comparable[] arr, int l, int r){ // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot swap( arr, l , (int)(Math.random()*(r-l+1))+l ); Comparable v = arr[l]; int j = l; // arr[l+1...j] < v ; arr[j+1...i) > v for( int i = l + 1 ; i <= r ; i ++ ) if( arr[i].compareTo(v) < 0 ){ j ++; swap(arr, j, i); } swap(arr, l, j); return j; }

然而，又遇见了问题。 不足：当数据重复的值很多时，会退化到O(n2)

3.双路快速排序

private static int partition(Comparable[] arr, int l, int r){ // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot swap( arr, l , (int)(Math.random()*(r-l+1))+l ); Comparable v = arr[l]; // arr[l+1...i) <= v; arr(j...r] >= v int i = l+1, j = r; while( true ){ // 注意这里的边界, arr[i].compareTo(v) < 0, 不能是arr[i].compareTo(v) <= 0 while( i <= r && arr[i].compareTo(v) < 0 ) i ++; // 注意这里的边界, arr[j].compareTo(v) > 0, 不能是arr[j].compareTo(v) >= 0 while( j >= l+1 && arr[j].compareTo(v) > 0 ) j --; if( i > j ) break; swap( arr, i, j ); i ++; j --; } swap(arr, l, j); return j; } // 递归使用快速排序,对arr[l...r]的范围进行排序 private static void sort(Comparable[] arr, int l, int r){ // 对于小规模数组, 使用插入排序 if( r - l <= 15 ){ InsertionSort.sort(arr, l, r); return; } int p = partition(arr, l, r); sort(arr, l, p-1 ); sort(arr, p+1, r); } public static void sort(Comparable[] arr){ int n = arr.length; sort(arr, 0, n-1); }

4.三路快速排序

// 递归使用快速排序,对arr[l...r]的范围进行排序 private static void sort(Comparable[] arr, int l, int r){ // 对于小规模数组, 使用插入排序 if( r - l <= 15 ){ InsertionSort.sort(arr, l, r); return; } // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot swap( arr, l, (int)(Math.random()*(r-l+1)) + l ); Comparable v = arr[l]; int lt = l; // arr[l+1...lt] < v int gt = r + 1; // arr[gt...r] > v int i = l+1; // arr[lt+1...i) == v while( i < gt ){ if( arr[i].compareTo(v) < 0 ){ swap( arr, i, lt+1); i ++; lt ++; } else if( arr[i].compareTo(v) > 0 ){ swap( arr, i, gt-1); gt --; } else{ // arr[i] == v i ++; } } swap( arr, l, lt ); sort(arr, l, lt-1); sort(arr, gt, r); } public static void sort(Comparable[] arr){ int n = arr.length; sort(arr, 0, n-1); }

六.堆排序

增加元素和取出元素：

// 像最大堆中插入一个新的元素 item public void insert(Item item){ assert count + 1 <= capacity; data[count+1] = item; count ++; shiftUp(count); } // 从最大堆中取出堆顶元素, 即堆中所存储的最大数据 public Item extractMax(){ assert count > 0; Item ret = data[1]; swap( 1 , count ); count --; shiftDown(1); return ret; }

最重要的shiftUp和shiftDown:

//******************** //* 最大堆核心辅助函数 //******************** private void shiftUp(int k){ while( k > 1 && data[k/2].compareTo(data[k]) < 0 ){ swap(k, k/2); k /= 2; } } private void shiftDown(int k){ while( 2*k <= count ){ int j = 2*k; // 在此轮循环中,data[k]和data[j]交换位置 if( j+1 <= count && data[j+1].compareTo(data[j]) > 0 ) j ++; // data[j] 是 data[2*k]和data[2*k+1]中的最大值 if( data[k].compareTo(data[j]) >= 0 ) break; swap(k, j); k = j; } }

HeapSort1:

// 对整个arr数组使用HeapSort1排序 // HeapSort1, 将所有的元素依次添加到堆中, 在将所有元素从堆中依次取出来, 即完成了排序 // 无论是创建堆的过程, 还是从堆中依次取出元素的过程, 时间复杂度均为O(nlogn) // 整个堆排序的整体时间复杂度为O(nlogn) public static void sort(Comparable[] arr){ int n = arr.length; MaxHeap<Comparable> maxHeap = new MaxHeap<Comparable>(n); for( int i = 0 ; i < n ; i ++ ) maxHeap.insert(arr[i]); for( int i = n-1 ; i >= 0 ; i -- ) arr[i] = maxHeap.extractMax(); }

HeapSort2:

// 构造函数, 通过一个给定数组创建一个最大堆 // 该构造堆的过程, 时间复杂度为O(n) public MaxHeap(Item arr[]){ int n = arr.length; data = (Item[])new Comparable[n+1]; capacity = n; for( int i = 0 ; i < n ; i ++ ) data[i+1] = arr[i]; count = n; for( int i = count/2 ; i >= 1 ; i -- ) shiftDown(i); } // 对整个arr数组使用HeapSort2排序 // HeapSort2, 借助我们的heapify过程创建堆 // 此时, 创建堆的过程时间复杂度为O(n), 将所有元素依次从堆中取出来, 实践复杂度为O(nlogn) // 堆排序的总体时间复杂度依然是O(nlogn), 但是比HeapSort1性能更优, 因为创建堆的性能更优 public static void sort(Comparable[] arr){ int n = arr.length; MaxHeap<Comparable> maxHeap = new MaxHeap<Comparable>(arr); for( int i = n-1 ; i >= 0 ; i -- ) arr[i] = maxHeap.extractMax(); }

七.算法的性能测试

比较百万级别的数据，O(n2)的算法不合适。

所以只比较O(nlogn)的算法 比较归并，二路快排，三路快排的效率：

public static void main(String[] args) { int N = 1000000; // 测试1 一般性测试 System.out.println("Test for random array, size = " + N + " , random range [0, " + N + "]"); Integer[] arr1 = SortTestHelper.generateRandomArray(N, 0, N); Integer[] arr2 = Arrays.copyOf(arr1, arr1.length); Integer[] arr3 = Arrays.copyOf(arr1, arr1.length); SortTestHelper.testSort("quick_three.MergeSort", arr1); SortTestHelper.testSort("quick_three.QuickSort2Ways", arr2); SortTestHelper.testSort("quick_three.QuickSort3Ways", arr3); System.out.println(); // 测试2 测试近乎有序的数组 int swapTimes = 100; assert swapTimes >= 0; System.out.println("Test for nearly ordered array, size = " + N + " , swap time = " + swapTimes); arr1 = SortTestHelper.generateNearlyOrderedArray(N, swapTimes); arr2 = Arrays.copyOf(arr1, arr1.length); arr3 = Arrays.copyOf(arr1, arr1.length); SortTestHelper.testSort("quick_three.MergeSort", arr1); SortTestHelper.testSort("quick_three.QuickSort2Ways", arr2); SortTestHelper.testSort("quick_three.QuickSort3Ways", arr3); System.out.println(); // 测试3 测试存在包含大量相同元素的数组 System.out.println("Test for random array, size = " + N + " , random range [0,10]"); arr1 = SortTestHelper.generateRandomArray(N, 0, 10); arr2 = Arrays.copyOf(arr1, arr1.length); arr3 = Arrays.copyOf(arr1, arr1.length); SortTestHelper.testSort("quick_three.MergeSort", arr1); SortTestHelper.testSort("quick_three.QuickSort2Ways", arr2); SortTestHelper.testSort("quick_three.QuickSort3Ways", arr3); return; }

比较结果： 对于包含有大量重复数据的数组, 三路快排有巨大的优势，对于一般性的随机数组和近乎有序的数组, 三路快排的效率虽然不是最优的, 但是是在非常可以接受的范围里，因此, 在一些语言中, 三路快排是默认的语言库函数中使用的排序算法。比如Java:)

加上推排序进行比较：