【Java数据结构】常见排序详解 |
您所在的位置：网站首页 › java自动排序的数据结构 › 【Java数据结构】常见排序详解 |
【Java数据结构】常见排序详解
|
文章目录
一、排序的概念和分类1.排序的基本概念2.排序的稳定性
二、常见排序1.直接插入排序2.希尔排序3.简单选择排序4.堆排序5.冒泡排序6.快速排序6.1.递归快速排序6.1.1.快排优化
6.2.非递归方式实现
7.归并排序7.1.递归归并排序7.2.非递归归并排序
总结
一、排序的概念和分类
1.排序的基本概念
排序是将一批无序的记录(数据)重新排列成按关键字有序的记录序列的过程。 排序分为内部排序和外部排序 若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程 2.排序的稳定性假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。 总结起来就是，如果一个数据在排序过程中发生了跳跃行为，则为不稳定的排序；反之，则是稳定的排序。
直接插入排序的基本操作是讲一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。 代码： public static void insertSort(int[] array) { for (int i = 1; i if(array[j] > tmp) { array[j+1] = array[j]; }else { break; } } //j回退到了小于0的地方 array[j+1] = tmp; } }流程图解：
所以最好的情况就是我们原来需要的排序的元素之间就是有序的，比如说{1，2，3，4，5，6}，那么我们需要比较的次数，其实就是临近两个元素的比较，因此没有移动的记录，时间复杂度为O(n)； 最坏的情况就是元素都是逆序的，如{6，5，4，3，2，1}，所以都需要比较，移动次数达到O（n^2）. 稳定性：稳定 插入排序，初始数据越接近有序，时间效率越高 2.希尔排序希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。 希尔对记录的分组，不是简单地“逐段分割”，而是将相隔某个“增量”的记录分成一组。 在严薇敏的《数据结构》里面是这样说的：
上面的话可能有点难理解，下面我们通过画图来了解一下希尔排序的本质。 希尔排序跟直接插入排序有点相似，可以说是直接插入排序的升级版。不同在于，希尔排序的比较方式变成了跳跃式的。比如说下面这组数据的第一次排序。
最终排序完成了。
我们来看一下希尔排序的代码： public static void shell(int[] array,int gap) { for (int i = gap; i if(array[j] > tmp) { array[j+gap] = array[j]; }else { break; } } array[j+gap] = tmp; } } //按照5、3、1分组 public static void shellSort1(int[] array) { int[] drr = {5,3,1}; for (int i = 0; i for (int i = 0; i //1 2 3 4 5 6 if(array[j] int tmp = array[i]; array[i] = array[j]; array[j] = tmp;
有时候，我们可能不需要循环那么多次，循环一两次就有序了，如果在有序的序列中继续循环，则会造成时间的浪费。为避免这种情况，所以我们可以对代码进行稍稍改进： public static void selectSort(int[] array) { for (int i = 0; i //找到最小值下标 if(array[j] //1、建堆 O(N) createHeap(array); int end = array.length-1; //2、交换然后调整 O(N * log N) while (end > 0) { swap(array,0,end); shiftDown(array,0,end); end--; } } public static void createHeap(int[] array) { for (int parent = (array.length-1-1)/2; parent >= 0 ; parent--) { shiftDown(array,parent,array.length); } } public static void shiftDown(int[] array,int parent,int len) { int child = 2*parent+1;//左孩子下标 while (child child++; } //child下标 就是左右孩子最大值的下标 if(array[child] > array[parent]) { swap(array,child,parent); parent = child; child = 2*parent+1; }else { break; } } }复杂度分析： 时间复杂度：O(n * log2(n))——2指的是以2为底空间复杂度：O(1)稳定性：不稳定 【注意】 堆排序只能用于顺序结构，不能用于链式结构由于建初堆的时候所需比较的次数较多，因此记录次数较少时不宜采用。 5.冒泡排序冒泡排序是一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。
复杂度分析： 时间复杂度：O(N^2)空间复杂度：O(1)稳定性：稳定。 6.快速排序 6.1.递归快速排序快速排序是冒泡排序的升级版，它们都属于交换排序类，即它也是通过不断比较和移动交换来实现排序，不同的是，快排的实现增大的了记录的比较和移动的距离。 快排将关键字较大的数据从前面直接移到后面，关键字较小的记录从后面直接移到前面，从而减少了总的比较次数和移动交换次数。 快排的基本思想： 通过一趟排序将待排序的数据分割成独立的两部分，其中一部分比另一部小，然后再分别对这两部分记录并再次进行排序，以达到整个序列有序。 我们翻译翻译一下上面的那段话： 首先，你得有一个中间数，比它小的放一边，比它大的放一边。这个数，我们称为基准值。采用分治思想，对左右两个小区间按照同样的方式处理，直到小区间的长度 == 1，代表已经有序，或者小区间的长度 == 0，代表没有数据。可能大家看到这里也还是有点迷惑，我们直接上代码。 public static void quickSort(int[] array) { quick(array,0,array.length-1); } public static void quick(int[] array,int left,int right) { if(left >= right) { return; } int pivot = partition(array,left,right);//基准 quick(array,left,pivot-1); quick(array,pivot+1,right); }上面的代码是不是有点像二叉树的遍历？ 这二者确实有相似之处，我们后面再讲。 上面还有一个partition函数，这个函数是我们快速排序最关键的地方。 /** * 找基准 * @param array 待排序数组对象 * @param start左边界 * @param end右边界 * @return 基准值下标 */ private static int partition(int[] array,int start,int end) { int tmp = array[start]; while (start end--; } //end下标就遇到了 < tmp的值 array[start] = array[end]; while (start int mid = start + ((end-start) >>> 1); if(array[start] return start; }else if(array[mid] > array[end]) { return end; }else { return mid; } }else { if(array[mid] > array[start]) { return start; }else if(array[mid] return mid; } } }前面quick函数改动一下，如下： public static void quick(int[] array,int left,int right) { if(left >= right) { return; } //采用三数取中法找基准值 int midValIndex = findMidValIndex(array,left,right); swap(array,midValIndex,left); int pivot = partition(array,left,right);//基准 quick(array,left,pivot-1); quick(array,pivot+1,right); }其实，优化到这里已经很棒了 。但是，我们还能优化。 这里先插播一个知识点： 直接插入是简单排序中性能最好的。 所以如果要我们要排序的数组非常小，直接插入排序会更好。 原因在于，快速排序用到了递归操作，在大量的数据排序时，这点性能影响相对它的整体算法优势而言是可以忽略的。但是如果数组只有不多的数据需要排序，就有点大材小用了。 因此，我们在这里的优化是： 增加一个判断，当 right-left+1 不大于某个常数时，就用直接插入排序，这个常数是具体情况而定。这样我们就能保证最大化地利用两种排序的优势来完成排序工作了。 /** * 优化，加入插入排序 * @param array 待排序数组对象 * @param left 左边界 * @param right 右边界 * @return 基准值下标 */ public static void quick(int[] array,int left,int right) { if(left >= right) { return; } //加一个判断，如果区间内的数据，在排序的过程当中，小于某个范围了，可以使用直接插入排序 if(right-left+1 for (int i = 1; i if(array[j] > tmp) { array[j+1] = array[j]; }else { break; } } array[j+1] = tmp; } } 6.2.非递归方式实现我们都知道，递归对性能是有一定影响的。所以我们也可以采用非递归的方式来实现快速排序
mergeSortInternal函数的图解： 其实就是对半分开数组
而其本质，其实就是合并两个数组，并使其有序起来。 merge函数的代码： private static void merge(int[] array,int low,int mid,int high) { int[] tmp = new int[high-low+1]; int k = 0;// int s1 = low; int e1 = mid; int s2 = mid+1; int e2 = high; while (s1 tmp[k++] = array[s1++]; }else { tmp[k++] = array[s2++]; } } while (s1 tmp[k++] = array[s2++]; } //拷贝tmp数组的元素 放入原来的数组array当中 for (int i = 0; i int nums = 1;//每组的数据个数 while (nums int left = i; int mid = left+nums-1; //防止越界 if(mid >= array.length) { mid = array.length-1; } int right = mid+nums; //防止越界 if(right >= array.length) { right = array.length-1; } //小标确定之后，进行合并 merge(array,left,mid,right); } nums *= 2;数组合并后，以1-2-4-8-16-进行循环 } }图解如下：
这次常见排序的文章，来来回回写了两天左右，在写的过程，也是学习的过程，特别是里面画图的时候，得理清楚整个排序的思想，才能很好的作出整个图解出来。各位看客老爷们，希望看到能给个三连，感谢！ |
时间和复杂度分析： 我们在实现的这个排序算法的时候，只借助了一个辅助的记录空间。
代码：
这里这个merge函数是归并排序里面的关键，无论是采用递归还是非递归都必须采用到这部分的函数。
【本文地址】
今日新闻 |
推荐新闻 |