java自动排序的数据结构,java基本数据类型排序

　　00-1010一、排序的概念和分类1。排序的基本概念2。排序的稳定性2。常见排序1。直接插入排序2。希尔排序3。简单选择排序4。堆排序5。冒泡排序6。快速排序6.1。递归快速排序6.2。非递归方式实现7。递归合并排序7.2。非递归合并排序概述

目录

　　00-1010排序是将一批无序的记录(数据)重新排列成按关键字排序的记录序列的过程。

　　排序分为内部排序和外部排序。

　　如果整个排序过程可以在不访问外存的情况下完成，这种排序问题称为内部排序。相反，如果参与排序的记录数量非常大，整个序列的排序过程无法在内存中完成，这种排序问题就叫做外部排序。内部排序过程是一个逐渐扩大有序记录序列长度的过程。

　　00-1010假设在要排序的记录序列中有许多具有相同关键字的记录。如果排序，这些记录的相对顺序将保持不变，即在原序列中，r[i]=r[j]，r[i]在r[j]之前，但在排序后的序列中，r[i]仍在r[j]中。否则就叫不稳定。

　　综上所述，如果一个数据在排序过程中出现跳跃，就是不稳定排序；相反，它是一种稳定的类型。

　　时间复杂度：算法执行的时间和空间复杂度：运行一个程序所需的内存量。

一、排序的概念和分类

　　00-1010直接插入排序的基本操作是在有序表中插入一条记录，从而得到记录数增加1的新的有序表。

　　代码：

　　public static void insertSort(int[]array){ for(int I=1；I数组.长度；I){ int tmp=array[I]；int j=I-1；for(；j=0；j-){ 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)。

　　稳定性：稳定性

　　插入，初始数据越接近顺序，时间效率越高。

　　00-1010希尔排序法也叫减量增量法。希尔排序法的基本思想是：首先选取一个整数，将待排序文件中的所有记录分组，距离为0的所有记录都在同一组中，对每组中的记录进行排序。然后，重复上面的分组和排序。当达到=1时，所有记录都在统一组中排序。

　　希尔对记录的分组不是简单的“一段一段”，而是以一定的“增量”分隔的一组记录。

　　严为民的《数据结构》是这样说的：

　　上面的话可能有点难以理解。让我们通过画图来了解希尔排序的本质。

　　Hill排序类似于直接插入排序，可以说是直接插入排序的升级版。不同的是，希尔排序的比较法变成了飞跃。比如下面数据的第一次排序。

　　最后，排序完成。

　　让我们来看看希尔排序的代码：

　　公共静态void shell(int[] array，int gap){ for(int I=gap；I数组.长度；我

　　+ ) { int tmp = array[i]; int j = i-gap; for (; j >= 0 ; j -= gap) { 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 < drr.length; i++) { shell(array,drr[i]); } }是不是跟直接插入排序很像？所以我们才说，希尔排序是直接插入排序的升级版。它不是随便分组后各自排序，而是将相隔某个增量gap的记录组成一个子序列，实现跳跃式移动，使得排序的效率提高了。

　　所以，选取增量是非常关键的一步，值得一提的是，选取什么样的增量，目前为止尚没有一个没完美的增量序列。

　　复杂度分析：

　　时间复杂度[和增量有关系的]：O(n^1.3 - n^1.5)。空间复杂度：O(1)稳定性：不稳定的。

3.简单选择排序

简单选择排序：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第 i(1 ≤ i ≤n) 个记录交换

 public static void selectSort1(int[] array) { for (int i = 0; i < array.length; i++) { for (int j = i+1; j < array.length; j++) { //1 2 3 4 5 6 if(array[j] < array[i]) { swap(array,i,j); } } } } public static void swap(int[] array,int i,int j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp;

　　有时候，我们可能不需要循环那么多次，循环一两次就有序了，如果在有序的序列中继续循环，则会造成时间的浪费。为避免这种情况，所以我们可以对代码进行稍稍改进：

 public static void selectSort(int[] array) { for (int i = 0; i < array.length; i++) { int minIndex = i; for (int j = i+1; j < array.length; j++) { //找到最小值下标 if(array[j] < array[minIndex]) { minIndex = j; } } swap(array,i,minIndex); } }

复杂度分析：

　　时间复杂度：O(n^2)空间复杂度：同接下介绍的冒泡排序一样，只有在两个记录交换时需要一个辅助空间，所以空间复杂度为O(1).稳定性：稳定

4.堆排序

堆排序的基本原理也是选择排序，只是不在使用遍历的方式查找无序区间的最大的数，而是通过堆来选择无序区间的最大的数。

　　我上一篇文章有详细介绍，这里就不再说了，大家感兴趣可以去了解一下。 Java数据结构之优先级队列(堆)图文详解

　　这里也给一下代码：

 public static void heapSort(int[] array) { //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 < len) { if(child+1 < len && array[child] < array[child+1]) { 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.冒泡排序

冒泡排序是一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

　　代码：

 public static void bubbleSort(int[] array) { for (int i = 0; i < array.length-1; i++) { for (int j = 0; j < array.length-1; j++) { if(array[j] > array[j+1]) { swap(array,j+1,j); } } } } public static void swap(int[] array,int i,int j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp;

复杂度分析：

　　时间复杂度：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) { while (start < end && array[end] >= tmp) { end--; } //end下标就遇到了 < tmp的值 array[start] = array[end]; while (start < end && array[start] <= tmp) { start++; } //start下标就遇到了 > tmp的值 array[end] = array[start]; } array[start] = tmp; return start; }

我们下面通过图解模拟一下函数的运行过程：

　　可以看到，当第一轮走完之后，数据由基准值分成了两部分。

　　之后，我们再次对左右两部分完成同样的操作，如下：

　　一直递归下来，跟二叉树的遍历类似。

　　复杂度分析：

　　时间复杂度：

　　最好情况下：O（nlogn）最坏情况下：O（n^2）.空间复杂度：O（logn）

　　稳定性：不稳定

　　快排优化不知大家看上面的图解的时候有没有一点困惑，就是我们这基准选得不好，导致第一趟递归下来的效果不好，变成了如下图：

　　如果我们有一种办法，先找到相对居中的那个数字，那么整个排序的时间复杂度是不是大大减小了。

　　于是，有人提出了随机选取一个值来作为基准，称为随机选取法。

　　这种做法，得看运气，因为假如选的好，刚刚选取中间值，那么，性能大大提高；如果随机得不好，比如随机到最小值或者最大值，那么性能则变成最差了。

　　所以有人提出一个新的方法，三数取中：

　　取三个关键字先进行排序，将中间数作为基准，一般取左端，右端和中间三个数。

　　如果运用三数取中这种方法的话，第一次比较的结果如下：

　　可以看到，11基本上与中间的数字相差不远了，性能大大提高。

　　所以，这里我们再写一个找基准的代码：

/** * 找基准 三数取中法 * @param array 待排序数组对象 * @param left 左边界 * @param right 右边界 * @return 基准值下标 */ private static int findMidValIndex(int[] array,int start,int end) { int mid = start + ((end-start) >>> 1); if(array[start] < array[end]) { if(array[mid] < 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] < array[end]) { return end; }else { 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 <= 1400) { //使用直接插入排序 insertSort2(array,left,right); return; } //1、找基准之前，我们找到中间大小的值-使用三数取中法 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); }//插入排序 public static void insertSort(int[] array,int start,int end) { for (int i = 1; i <= end; i++) { int tmp = array[i]; int j = i-1; for (; j >= start ; j--) { if(array[j] > tmp) { array[j+1] = array[j]; }else { break; } } array[j+1] = tmp; } }

6.2.非递归方式实现

我们都知道，递归对性能是有一定影响的。所以我们也可以采用非递归的方式来实现快速排序

/** * 快速排序非递归实现 * @param array 待排序数组 */ public static void quickSort(int[] array) { Stack<Integer> stack = new Stack<>(); int left = 0; int right = array.length-1; int pivot = partition(array,left,right); if(pivot > left+1) { stack.push(left); stack.push(pivot-1); } if(pivot < right-1) { stack.push(pivot+1); stack.push(right); } while (!stack.isEmpty()) { right = stack.pop(); left = stack.pop(); pivot = partition(array,left,right); if(pivot > left+1) { //左边有2个元素 stack.push(left); stack.push(pivot-1); } if(pivot < right-1) { //右边有2个元素 stack.push(pivot+1); stack.push(right); } } }

非递归复杂度分析：

　　时间复杂度：

　　最坏情况下： O(n^2)平均情况下：O（nlogn）空间复杂度：

　　最坏情况下：O（n）平均情况下：O（logn）稳定性：不稳定

7.归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide an Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并

7.1.递归归并排序

直接上代码：

//调用了mergeSortInternal函数 public static void mergeSort1(int[] array) { mergeSortInternal(array,0,array.length-1); } private static void mergeSortInternal(int[] array,int low,int high) { if(low>=high) { return; } int mid = low + ((high-low) >>> 1);//>>>无符号右移1位。就是除以2，找中间值 //左边递归 mergeSortInternal(array,low,mid); //右边递归 mergeSortInternal(array,mid+1,high); //合并两边数组 merge(array,low,mid,high); }

mergeSortInternal函数的图解：

　　其实就是对半分开数组

　　这里这个merge函数是归并排序里面的关键，无论是采用递归还是非递归都必须采用到这部分的函数。

　　而其本质，其实就是合并两个数组，并使其有序起来。

　　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 <= e1 && s2 <= e2) { if(array[s1] <= array[s2]) { tmp[k++] = array[s1++]; }else { tmp[k++] = array[s2++]; } } while (s1 <= e1) { tmp[k++] = array[s1++]; } while (s2 <= e2) { tmp[k++] = array[s2++]; } //拷贝tmp数组的元素 放入原来的数组array当中 for (int i = 0; i < k; i++) { array[i+low] = tmp[i]; } }

7.2.非递归归并排序

归并排序除了用递归的方式来实现，也可以用非递归的方式来实现。

 public static void mergeSort(int[] array) { int nums = 1;//每组的数据个数 while (nums < array.length) { //数组每次都要进行遍历,确定要归并的区间 for (int i = 0; i < array.length; i += nums*2) { 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-进行循环 } }

图解如下：

总结

这次常见排序的文章，来来回回写了两天左右，在写的过程，也是学习的过程，特别是里面画图的时候，得理清楚整个排序的思想，才能很好的作出整个图解出来。各位看客老爷们，希望看到能给个三连，感谢！

　　到此这篇关于Java数据结构常见几大排序梳理的文章就介绍到这了,更多相关Java 排序内容请搜索盛行IT以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。