十大经典排序算法总结（含Java代码实现）

6.3 代码实现

/** 
 * 快速排序方法 
 * @param array 
 * @param start 
 * @param end 
 * @return 
 */ 
 public static int[] QuickSort(int[] array, int start, int end) { 
 if (array.length < 1 || start < 0 || end >= array.length || start > end) return null; 
 int smallIndex = partition(array, start, end); 
 if (smallIndex > start) 
 QuickSort(array, start, smallIndex - 1); 
 if (smallIndex < end) 
 QuickSort(array, smallIndex + 1, end); 
 return array; 
 } 
 /** 
 * 快速排序算法——partition 
 * @param array 
 * @param start 
 * @param end 
 * @return 
 */ 
 public static int partition(int[] array, int start, int end) { 
 int pivot = (int) (start + Math.random() * (end - start + 1)); 
 int smallIndex = start - 1; 
 swap(array, pivot, end); 
 for (int i = start; i <= end; i++) 
 if (array[i] <= array[end]) { 
 smallIndex++; 
 if (i > smallIndex) 
 swap(array, i, smallIndex); 
 } 
 return smallIndex; 
 } 
 /** 
 * 交换数组内两个元素 
 * @param array 
 * @param i 
 * @param j 
 */ 
 public static void swap(int[] array, int i, int j) { 
 int temp = array[i]; 
 array[i] = array[j]; 
 array[j] = temp; 
 } 

6.4 算法分析

最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(nlogn)

7、堆排序(Heap Sort)

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于(或者大于)它的父节点。堆排序：堆排序

7.1 算法描述

将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区;

将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n];

由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

7.2 动图演示

7.3 代码实现

注意：这里用到了完全二叉树的部分性质：

http://www.cnblogs.com/guoyaohua/p/8595289.html

//声明全局变量，用于记录数组array的长度； 
static int len; 
 /** 
 * 堆排序算法 
 * 
 * @param array 
 * @return 
 */ 
 public static int[] HeapSort(int[] array) { 
 len = array.length; 
 if (len < 1) return array; 
 //1.构建一个最大堆 
 buildMaxHeap(array); 
 //2.循环将堆首位（最大值）与末位交换，然后在重新调整最大堆 
 while (len > 0) { 
 swap(array, 0, len - 1); 
 len--; 
 adjustHeap(array, 0); 
 } 
 return array; 
 } 
 /** 
 * 建立最大堆 
 * 
 * @param array 
 */ 
 public static void buildMaxHeap(int[] array) { 
 //从最后一个非叶子节点开始向上构造最大堆 
 for (int i = (len/2 - 1); i >= 0; i--) { //感谢 @让我发会呆 网友的提醒，此处应该为 i = (len/2 - 1)  
 adjustHeap(array, i); 
 } 
 } 
 /** 
 * 调整使之成为最大堆 
 * 
 * @param array 
 * @param i 
 */ 
 public static void adjustHeap(int[] array, int i) { 
 int maxIndex = i; 
 //如果有左子树，且左子树大于父节点，则将最大指针指向左子树 
 if (i * 2 < len && array[i * 2] > array[maxIndex]) 
 maxIndex = i * 2; 
 //如果有右子树，且右子树大于父节点，则将最大指针指向右子树 
 if (i * 2 + 1 < len && array[i * 2 + 1] > array[maxIndex]) 
 maxIndex = i * 2 + 1; 
 //如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。 
 if (maxIndex != i) { 
 swap(array, maxIndex, i); 
 adjustHeap(array, maxIndex); 
 } 
 } 

7.4 算法分析

最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(nlogn) 平均情况：T(n) = O(nlogn)

8、计数排序(Counting Sort)

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

（编辑：晋中站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!