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

4.3 代码实现

/** 
 * 希尔排序 
 * 
 * @param array 
 * @return 
 */ 
 public static int[] ShellSort(int[] array) { 
 int len = array.length; 
 int temp, gap = len / 2; 
 while (gap > 0) { 
 for (int i = gap; i < len; i++) { 
 temp = array[i]; 
 int preIndex = i - gap; 
 while (preIndex >= 0 && array[preIndex] > temp) { 
 array[preIndex + gap] = array[preIndex]; 
 preIndex -= gap; 
 } 
 array[preIndex + gap] = temp; 
 } 
 gap /= 2; 
 } 
 return array; 
 } 

4.4 算法说明

最佳环境：T(n) = O(nlog2 n) 最坏环境：T(n) = O(nlog2 n) 均匀环境：T(n) =O(nlog2n)

5、合并排序(Merge Sort)

和选择排序一样，合并排序的机能不受输入数据的影响，但示意比选择排序好的多，由于始终都是O(n log n)的时刻伟大度。价钱是必要特另外内存空间。合并排序：合并排序

合并排序是成立在合并操纵上的一种有用的排序算法。该算法是回收分治法(Divide and Conquer)的一个很是典范的应用。合并排序是一种不变的排序要领。将已有序的子序列归并，获得完全有序的序列;即先使每个子序列有序，再使子序列段间有序。若将两个有序表归并成一个有序表，称为2-路合并。

5.1 算法描写

把长度为n的输入序列分成两个长度为n/2的子序列;

对这两个子序列别离回收合并排序;

将两个排序好的子序列归并成一个最终的排序序列。

5.2 动图演示

5.3 代码实现

/** 
 * 合并排序 
 * 
 * @param array 
 * @return 
 */ 
 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)); 
 } 
 /** 
 * 合并排序——将两段排序好的数组团结成一个排序数组 
 * 
 * @param left 
 * @param right 
 * @return 
 */ 
 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; 
 } 

5.4 算法说明

最佳环境：T(n) = O(n) 最差环境：T(n) = O(nlogn) 均匀环境：T(n) = O(nlogn)

6、快速排序(Quick Sort)

快速排序的根基头脑：通过一趟排序将待排记录脱离成独立的两部门，个中一部门记录的要害字均比另一部门的要害字小，则可别离对这两部门记录继承举办排序，以到达整个序列有序。快速排序：快速排序

6.1 算法描写

快速排序行使分治法来把一个串(list)分为两个子串(sub-lists)。详细算法描写如下：

从数列中挑出一个元素，称为 “基准”(pivot);

从头排序数列，全部元素比基准值小的摆放在基准前面，全部元素比基准值大的摆在基准的后头(沟通的数可以到任一边)。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区(partition)操纵;

递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

6.2 动图演示

（编辑：河北网）

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