五种常见的排序实现
算法描述 1.插入排序从第一个元素开始,该元素可以认为已经被排序
取出下一个元素,在已经排序的元素序列中从后向前扫描 如果该元素(已排序)大于新元素,将该元素移到下一位置 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置 将新元素插入到该位置后 重复步骤2~5在这个基础上有衍生出提高效率的二分插入排序
2.冒泡排序
比较相邻的元素。如果第一个比第二个大,就交换他们两个。
对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。 针对所有的元素重复以上的步骤,除了最后一个。 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。最简单的排序,名字很形象,排序元素会呈现上浮或者下沉的特点,
3.希尔排序
先取一个正整数 d1(d1 < n),把全部记录分成 d1 个组,所有距离为 d1 的倍数的记录看成一组,然后在各组内进行插入排序
然后取 d2(d2 < d1) 重复上述分组和排序操作;直到取 di = 1(i >= 1) 位置,即所有记录成为一个组,最后对这个组进行插入排序。一般选 d1 约为 n/2,d2 为 d1 /2, d3 为 d2/2 ,…, di = 1。 希尔排序是基于插入排序的以下两点性质而提出改进方法的: 插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率 但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位 4.堆排序堆的特点
通常堆是通过一维数组来实现的。在数组起始位置为0的情形中: 父节点i的左子节点在位置(2*i+1); 父节点i的右子节点在位置(2*i+2); 子节点i的父节点在位置floor((i-1)/2); 在堆的中,堆中的最大值总是位于根节点(在优先队列中使用堆的话堆中的最小值位于根节点)。堆中定义以下几种操作: 最大堆调整(Max_Heapify):将堆的末端子节点作调整,使得子节点永远小于父节点 创建最大堆(Build_Max_Heap):将堆所有数据重新排序 堆排序(HeapSort):移除位在第一个数据的根节点,并做最大堆调整的递归运算5.归并排序
迭代法
申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列 设定两个指针,最初位置分别为两个已经排序序列的起始位置 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置 重复步骤3直到某一指针到达序列尾 将另一序列剩下的所有元素直接复制到合并序列尾 递归法 原理如下(假设序列共有n个元素): 将序列每相邻两个数字进行归并操作,形成 {\displaystyle floor(n/2)} floor(n/2)个序列,排序后每个序列包含两个元素 将上述序列再次归并,形成 {\displaystyle floor(n/4)} floor(n/4)个序列,每个序列包含四个元素 重复步骤2,直到所有元素排序完毕6.快速排序
从数列中挑出一个元素,称为”基准”(pivot),
重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。性能测试的结果
少量数据
insertionSort正序数列:808000nsinsertionSort倒序数列:793900nsinsertionSort随机数列:448300nsinsertionSort周期数列:92400nsbubbleSort正序数列:461500nsbubbleSort倒序数列:856000nsbubbleSort随机数列:539500nsbubbleSort周期数列:140100nsshellSort正序数列:34000nsshellSort倒序数列:55600nsshellSort随机数列:67900nsshellSort周期数列:35700nsheapSort正序数列:175700nsheapSort倒序数列:89500nsheapSort随机数列:37100nsheapSort周期数列:33800nsmergeSort正序数列:123100nsmergeSort倒序数列:118400nsmergeSort随机数列:112100nsmergeSort周期数列:55100nsquickSort正序数列:62100nsquickSort倒序数列:80200nsquickSort随机数列:78900nsquickSort周期数列:65200ns大量数据insertionSort正序数列:1599364000nsinsertionSort倒序数列:1586157400nsinsertionSort随机数列:869768700nsinsertionSort周期数列:593637800nsbubbleSort正序数列:499915700nsbubbleSort倒序数列:957839500nsbubbleSort随机数列:3328836500nsbubbleSort周期数列:495209600nsshellSort正序数列:3259400nsshellSort倒序数列:4043100nsshellSort随机数列:6653900nsshellSort周期数列:741600nsheapSort正序数列:3603700nsheapSort倒序数列:4112400nsheapSort随机数列:5584600nsheapSort周期数列:3804700nsmergeSort正序数列:5240900nsmergeSort倒序数列:2643600nsmergeSort随机数列:6001700nsmergeSort周期数列:2989600nsquickSort正序数列:2126000nsquickSort倒序数列:3228400nsquickSort随机数列:5726800nsquickSort周期数列:2121000ns/** Sort.java* Version 1.0.0* Created on 2017年4月27日* Copyright ReYo.Cn*/package reyo.sdk.utils.test.map;import java.lang.reflect.InvocationTargetException;import java.lang.reflect.Method;public class Sort { public static void main(String[] args) throws NoSuchMethodException, SecurityException, IllegalAccessException, IllegalArgumentException, InvocationTargetException { Sort s1 = new Sort(); System.out.println("少量数据"); int arraySize = 200; s1.test("insertionSort", arraySize); s1.test("bubbleSort", arraySize); s1.test("shellSort", arraySize); s1.test("heapSort", arraySize); s1.test("mergeSort", arraySize); s1.test("quickSort", arraySize); System.out.println("大量数据"); arraySize = 50000; s1.test("insertionSort", arraySize); s1.test("bubbleSort", arraySize); s1.test("shellSort", arraySize); s1.test("heapSort", arraySize); s1.test("mergeSort", arraySize); s1.test("quickSort", arraySize); } // 测试的脚手架 public void test(String methodName, int size) throws NoSuchMethodException, SecurityException, IllegalAccessException, IllegalArgumentException, InvocationTargetException { Method m1 = this.getClass().getMethod(methodName, int[].class); int[] test1 = new int[size]; int[] test2 = new int[size]; int[] test3 = new int[size]; int[] test4 = new int[size]; Sort sorttest = new Sort(); // 正序 for (int i = 0; i < size; i++) { test1[i] = i; } // 倒序 for (int i = 0; i < size; i++) { test2[i] = size - i; } // 乱序,随机,基本无重复元素 for (int i = 0; i < size; i++) { test3[i] = (int) (Math.random() * size); } // 大量重复元素 for (int i = 0; i < size; i++) { test4[i] = i + 50 % 50; } long startTime = System.nanoTime(); long endTime = System.nanoTime(); m1.invoke(sorttest, test1); startTime = System.nanoTime(); m1.invoke(sorttest, test1); endTime = System.nanoTime(); System.out.println(methodName + "正序数列:" + (endTime - startTime) + "ns"); startTime = System.nanoTime(); m1.invoke(sorttest, test2); endTime = System.nanoTime(); System.out.println(methodName + "倒序数列:" + (endTime - startTime) + "ns"); startTime = System.nanoTime(); m1.invoke(sorttest, test3); endTime = System.nanoTime(); System.out.println(methodName + "随机数列:" + (endTime - startTime) + "ns"); startTime = System.nanoTime(); m1.invoke(sorttest, test4); endTime = System.nanoTime(); System.out.println(methodName + "周期数列:" + (endTime - startTime) + "ns"); System.out.println(); } // 插入排序,稳定排序 // 插入排序由N-1趟排序组成,时间最好O(n),最坏O(n2),平均O(n2) // 空间O(1) public void insertionSort(int[] nums) { int j, p; int tmp; for (p = 1; p < nums.length; p++) { tmp = nums[p]; for (j = p; j > 0; j--) { if (nums[j - 1] > tmp) nums[j] = nums[j - 1]; } nums[j] = tmp; } } // 冒泡排序,稳定排序 // 时间最好O(n),最坏O(n2),平均O(n2) // 空间O(1) public void bubbleSort(int[] nums) { int j, p; int tmp; // 沉水,大数被移动到尾段 for (p = 0; p < nums.length - 1; p++) { for (j = 0; j < nums.length - 1 - p; j++) { if (nums[j] > nums[j + 1]) { tmp = nums[j]; nums[j] = nums[j + 1]; nums[j + 1] = tmp; } } } // //气泡,小数浮动到首段 // for(p = 0; p < nums.length - 1;p++){ // for(j = nums.length - 1;j > p;j--){ // if(nums[j-1] > nums[j]){ // tmp = nums[j]; // nums[j] = nums[j-1]; // nums[j-1] = tmp; // } // } // } } // 希尔排序(缩小增量排序),不稳定排序 // 属于插入排序,时间最好O(n),最坏O(n2),平均O(n1.3) // 空间O(1) public void shellSort(int[] nums) { int gap = 1; // 增量 int i, j; int len = nums.length; int tmp; // 初始增量,shell排序的效率与增量设定有很大关系 while (gap < len / 3) gap = gap * 3 + 1; for (; gap > 0; gap /= 3) { for (i = gap; i < len; i++) { tmp = nums[i]; for (j = i - gap; j >= 0 && nums[j] > tmp; j -= gap) nums[j + gap] = nums[j]; nums[j + gap] = tmp; } } } // 堆排序,不稳定排序 // 时间 平均2nlogn - O(nlogn) // 空间O(1) // 排序方式 // 创建一个堆H[0..n-1] // 把堆首(最大值)和堆尾互换 // 把堆的尺寸缩小1,并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置 // 重复步骤2,直到堆的尺寸为1 public void heapSort(int[] nums) { int i; // 遍历所有结点,对不满足规则节点进行调整 for (i = nums.length / 2; i >= 0; i--) { PercDown(nums, i, nums.length); } for (i = nums.length - 1; i > 0; i--) { int tmp = nums[0]; nums[0] = nums[i]; nums[i] = tmp; PercDown(nums, 0, i); } } // 调整堆序 public void PercDown(int[] nums, int i, int length) { int child; int tmp; for (tmp = nums[i]; 2 * i + 1 < length; i = child) { child = 2 * i + 1; // 左儿子 if (child != length - 1 && nums[child + 1] > nums[child]) child++; // 选出左右子结点中的较大值 if (tmp < nums[child]) { // 父节点小于子节点,需要进行调整 nums[i] = nums[child]; } else break; } nums[i] = tmp; } // 归并排序 public void mergeSort(int[] nums) { int[] tmpArray = new int[nums.length]; mSort(nums, tmpArray, 0, nums.length - 1); } public void mSort(int[] nums, int[] tmps, int left, int right) { int center; if (left < right) { center = (left + right) / 2; mSort(nums, tmps, left, center); mSort(nums, tmps, center + 1, right); merge(nums, tmps, left, center + 1, right); } } // 空间归并 public void merge(int[] nums, int[] tmps, int lpos, int rpos, int rightEnd) { int i, leftEnd, numElements, tmpPos; leftEnd = rpos - 1; tmpPos = lpos; numElements = rightEnd - lpos + 1; while (lpos <= leftEnd && rpos <= rightEnd) { if (nums[lpos] <= nums[rpos]) tmps[tmpPos++] = nums[lpos++]; else tmps[tmpPos++] = nums[rpos++]; } while (lpos <= leftEnd) tmps[tmpPos++] = nums[lpos++]; while (rpos <= rightEnd) tmps[tmpPos++] = nums[rpos++]; for (i = 0; i < numElements; i++, rightEnd--) nums[rightEnd] = tmps[rightEnd]; } // 快速排序 // 理论上能保证不出现最坏情况:三数中值分割法 // 小规模排序,快速排序不如插入排序 public void quickSort(int[] nums) { qSort(nums, 0, nums.length - 1); } // 递归快速排序 public void qSort(int[] nums, int left, int right) { int i, j; int pivot; if (left + 3 <= right) { // 至少有4个数 pivot = median3(nums, left, right); i = left; j = right - 1; while (true) { // 先推进索引再判断,而不是先判断再决定要不要推进索引 // 这样避免了a[i]=a[j]=pivot,导致索引不会被推进,也不会跳出循环 while (nums[++i] < pivot) { } while (nums[--j] > pivot) { } if (i < j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } else break; } int tmp = nums[i]; nums[i] = nums[right - 1]; nums[right - 1] = tmp; qSort(nums, left, i - 1); qSort(nums, i + 1, right); } // 少于4个数,不再分割,用插入排序直接排序 else { int k, p; int tmp; for (p = 1; p < right - left + 1; p++) { tmp = nums[left + p]; for (k = p; k > 0; k--) { if (nums[left + k - 1] > tmp) nums[left + k] = nums[left + k - 1]; } nums[left + k] = tmp; } } } // 分割数组 public int median3(int[] nums, int left, int right) { int center = (left + right) / 2; if (nums[left] > nums[center]) { int tmp = nums[left]; nums[left] = nums[center]; nums[center] = tmp; } if (nums[left] > nums[right]) { int tmp = nums[left]; nums[left] = nums[right]; nums[right] = tmp; } if (nums[center] > nums[right]) { int tmp = nums[center]; nums[center] = nums[right]; nums[right] = tmp; } int tmp = nums[center]; nums[center] = nums[right - 1]; nums[right - 1] = tmp; return nums[right - 1]; }}