java数据结构-排序(自用记忆)

一.排序的概念:

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

内部排序：数据元素全部放在内存中的排序

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

二.常见排序算法

①直接插入排序：从第 2 个元素开始，逐个取出未排序区的元素，在已排序区从后往前找它该待的位置，把比它大的元素往后挪，最后把它插入进去。(对象是每一次遍历的) [直接插入排序对下一个数字与已排序区的数进行比较必须从后往前（右往左），才能高效腾出插入位置，这是由插入排序的核心逻辑决定的]
②希尔排序：规定d=初始然后递减，从开始到每隔d个的就连起来(可以连多个只要够！)然后把连在一起的直接插入排序(其实就是直接排序)，然后d自选递减的下一个，反正最后要到1(相当于对全部直接插入排序)
③交换排序→冒泡排序：冒泡排序就是从第1个开始排序，然后排完n-1和n后第n个必定是最大值/最小值，然后第二轮还是从第1个开始排序只是最后排的结果是n-2和n-1，然后重复上述步骤，序列从后往前越来越对
④快速排序(填坑)：先把最左边和最右边的数都放一个下标指针，然后把最左边的数当枢纽+这个位置留空。从右边开始如果找到<枢纽的数就填在左边的空，然后左边指针向右1格。然后开始看左边指针如果找到>枢纽 的就提空放在右空格，然后右指针左移1格(上面都是被填的指针向中间靠)。然后直到靠到两个指针重合就把当枢纽的放进去，以枢纽往两边分，分成两个区，这两个区在分别进行上述快速排序(到这进行两轮)。 最后执行几轮不确定！
⑤简单选择排序：每次都在未排序的里面选最小的放到已排序的最后一个
⑥堆排序:先按给的数组按顺序编号1,2...n,然后按层序遍历存在完全二叉树中，然后从第[n/2]向下取整开始往小的去按根≥子树(选最大)/根≤子树(选最小)来调整。注意从大到小调整完还要回去数字编号大的看会不会第二次排序错误！
注意：输出堆顶元素后，不需要重新完整排序整个堆，只需要从新的堆顶开始，向下做一次 “局部调整” 即可恢复堆的性质。
插入元素按层序遍历放在最后。然后以这个新节点开始向上进行排序
⑦归并排序： 初始从每组 1 个元素开始（天然有序），每轮合并后分组大小翻倍（2→4→8…），直到分组大小≥数组长度，一组内的直接排序就行
⑧基数排序：先创建下标从0-10的多个链表，按个位数，十位数，百位数(到最大位数)，位数一样的就放一起，先出现的放上面，后出现的放下面(类似一条横线下面挂坠)，然后按从左到右，每个从上到下写一遍，然后再按刚刚的排，不过变为按进一位排，最后排完最后一位数就会发现从小到大

下面均以从小到大排序为例

①插入排序(从小到大):把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列

public static void insertSort(int arr[]){//插入排序 for(int i=1;i<arr.length;i++){ int temp=arr[i]; int j=i-1; for(;j>=0;j--){ if(arr[j]>temp){ arr[j+1]=arr[j]; } else{ arr[j+1]=temp; break; } } arr[j+1]=temp; } }

for从1开始到length，因为下标为0的时候就1个，默认有序。

然后先把下标为i的存在临时变量temp中，然后定义一个for循环中的变量j(因为后面要用，所以在外面2定义j)，然后启动j的循环，从j=i-1开始不断--，每一次--，如果j的数值>t，那就让下标j+1处的值为下标j处的值（这个部分就是把比下标i处的值小的值往前排，留出位置给临时变量temp）

然后每循环一次就会j--，循环到j处比temp小(此时因为上一步前移，所以j+1处为空)，那就把temp赋给j+1处，然后break

最后要补一个那就把temp赋给j+1处，就是找到比前面已排序的数所有都小的情况

②希尔排序希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成多个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

public static void shellSort(int arr[]){ int gap=arr.length; while(gap>1){ gap=gap/2; shell(arr,gap); } } public static void shell(int arr[],int gap){//插入排序 for(int i=gap;i<arr.length;i++){ int temp=arr[i]; int j=i-gap; for(;j>=0;j=j-gap){ if(arr[j]>temp){ arr[j+gap]=arr[j]; } else{ arr[j+gap]=temp; break; } } arr[j+gap]=temp; } }

希尔排序需要两段方法，因为希尔排序的gap有影响，所以第一个方法是传入数组和gap

第二个方法才是排序，gap的取值方法有很多

主要看第二个方法：首先希尔排序就是分区块，然后每个区块进行插入排序

但是这里的分区是跳跃性的，不方便直接操作，但是如果我们从直接插入排序的原理去思考：首先第一个循环从1开始，也就是0的下一个，但是希尔排序是按i,i+gap,i+gap+gap...这样下去的，那就把gap当做没次--的单位，也就是-gap，这样就可以做到每一次i++都处理不同区间的一次排序，而不是 先排序完一个区间，在排序下一个区间

③选择排序:每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完

public static void selectSort(int arr[]){ for(int i=0;i<arr.length;i++){ int index=i; for(int j=i+1;j<arr.length;j++){ if(arr[index]>arr[j]){ index=j; } } int t=arr[index]; arr[index]=arr[i]; arr[i]=t; } }

依旧需要双指针，一个在后面(未排序序列中)选出最大/最小的，另一个在后面指向需要填入的位置

找到之后把最小的和需要填入的位置的值交换

④堆排序:堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

public static void heapSort(int arr[]){ createHeap(arr); int end=arr.length-1; while(end>0){ int t=arr[0]; arr[0]=arr[end]; arr[end]=t; siftDown(arr,0,end); end--; } } public static void createHeap(int arr[]){ for(int p=(arr.length-2)/2;p>=0;p--){ siftDown(arr,p,arr.length); } } public static void siftDown(int arr[],int p,int len){ int child=2*p+1; while(child<len){ if(child+1<arr.length&&arr[child]<arr[child+1]){ child++; } if(arr[child]>arr[p]){ int t=arr[child]; arr[child]=arr[p]; arr[p]=t; p=child; child=2*p+1; } else { break; } } }

首先是先把数组改成小根堆的结果，也就是执行createHeap

然后每一次都取出堆顶元素(最小的元素)，也就是交换堆顶和最后一个元素后，从0到最后一个元素的前一个元素进行一次向下调整(end--)，即可获得除去最小元素的新的小根堆

⑤交换排序：基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

交换排序-冒泡排序

public static void bobbleSort(int arr[]){ for(int i=0;i<arr.length-1;i++){ for(int j=0;j<arr.length-i-1;j++){ boolean flg=false; if(arr[j]>arr[j+1]){ int t=arr[j]; arr[j]=arr[j+1]; arr[j+1]=t; flg=true; } if(flg==false){ break; } } } }

很基础的排序，多了一个判断来优化，如果某一轮循环交换没有执行，说明已经完全有序了，无需继续进行下去，所以break

交换排序-快速排序：快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

快速排序有三种方法：

1. Hoare版(双指针交换版)

public static void quickSort(int arr[]){//快速排序-双指针法 quick(arr,0,arr.length-1); } public static void quick(int arr[],int start,int end){ if(start>=end){ return; } int pivot=partfun(arr,start,end); quick(arr,start,pivot-1); quick(arr,pivot+1,end); } public static int partfun(int arr[],int left,int right){ int temp=arr[left]; int templeft=left; while(left<right){ while(left<right&&arr[right]>=temp){//因为right先循环左移保证了templeft交换后基准值的左边仍然是比基准值小的 right--; } while(left<right&&arr[left]<=temp){//这里两个while都必须取等号，否则遇到跟基准值一样的数会死循环 left++; } int t=arr[left]; arr[left]=arr[right]; arr[right]=t; } int t=arr[left]; arr[left]=arr[templeft]; arr[templeft]=t; return left; }

其实这三个方法本质是两个方法，前两个方法可以合并成一个，只是传入的时候要手动输入0和arr.length

第二个方法：如果是start>=end，那就说明结束了，直接return

pivot是获取基准最后要填入的下标，用于分区的分界点

然后从start-pivot-1，pivot+1和end分别递归两次(不包括pivot是因为pivot左边全部<=pivot，右边全部>=pivot)

第三个方法：其实这个方法虽然返回的是最后基准填入的下标，但是在过程中完成了排序

先把基准也就是最左边的数临时存下来，然后再把基准的下标（也就是初始的left）保存，因为这个left是原始数组arr中元素的下标，防止丢失。然后从右边开始找，right会停在第一个比基准值小的数上，left同理。然后交换left下标和right下标。最后把基准值和相遇处(left=right)的值交换位置即可（因为第一个循环right先动，保证了相遇点的值一定是<temp基准值的）

2.挖坑法

public static void quickSort(int arr[]){//快速排序-双指针法 quick(arr,0,arr.length-1); } public static void quick(int arr[],int start,int end){ if(start>=end){ return; } int pivot=partfun(arr,start,end); quick(arr,start,pivot-1); quick(arr,pivot+1,end); } private static int partfun(int[] array, int left, int right) { int tmp = array[left]; while (left < right) { while (left < right && array[right] >= tmp) { right--; } array[left] = array[right]; while (left < right && array[left] <= tmp) { left++; } array[right] = array[left]; } array[left] = tmp; return left; }

区别只有partfun方法里：先把最左边的数当场基准值
然后从右边开始找到比基准值小的，填入left下标

再到左边开始找到比基准值大的，填入right

最后相遇点(left=right)是空的，填入基准值，然后返回此处下标

3.前后指针

public static void quickSort(int arr[]){//快速排序-双指针法 quick(arr,0,arr.length-1); } public static void quick(int arr[],int start,int end){ if(start>=end){ return; } int pivot=partfun(arr,start,end); quick(arr,start,pivot-1); quick(arr,pivot+1,end); } private static int partfun(int[] array, int left, int right) { int prev = left; int cur = left + 1; while (cur <= right) { if (array[cur] < array[left] && array[++prev] != array[cur]) { swap(array, cur, prev); } cur++; } swap(array, prev, left); return prev; } // 配套的 swap 方法（需要自行补充） private static void swap(int[] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; }

4.快速排序优化(待)

5.快速排序非递归(待)

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

public static void mergeSortTmp(int arr[],int left,int right){ if(left>=right){ return; } int mid=(left+right)/2; mergeSortTmp(arr,left,mid); mergeSortTmp(arr,mid+1,right); merge(arr,left,mid,right); } public static void merge(int arr[],int left,int mid,int right) { int temp[] = new int[right - left + 1]; int k = 0; int s1 = left; int e1 = mid; int s2 = mid + 1; int e2 = right; while (s1 <= e1 && s2 <= e2) { if (arr[s1] <= arr[s2]) { temp[k++] = arr[s1++]; } else { temp[k++] = arr[s2++]; } } while (s1 <= e1) { temp[k++] = arr[s1++]; } while (s2 <= e2) { temp[k++] = arr[s2++]; } for (int i = 0; i < temp.length; i++) { arr[left + i] = temp[i]; } }

依旧是两个方法：但是第二个是用来2个数组合并成一个数组的，为什么会有序？因为这个归并排序是从1→2→4→8这样合并每一个数组的，所以从1→2开始就是按有序排的，2→4也是两个有序的2合并，变成有序的4，以此类推

所以这里的思路是先取中，然后把左边进行一次递归，右边进行一次递归

然后把left，mid，right，放进2和1方法里进行合并

⑦计数排序:统计相同元素出现次数→根据统计的结果将序列回收到原来的序列中

public static void countSort(int arr[]){ int max=arr[0]; int min=arr[0]; for(int i=1;i<arr.length;i++){ if(arr[i]>max){ max=arr[i]; } if(arr[i]<min){ min=arr[i]; } } int len=max-min+1; int count[]=new int[len]; for(int i=0;i<arr.length;i++){ int index=arr[i]; count[index-min]++; } int index=0; for(int i=0;i<count.length;i++){ while(count[i]!=0){ arr[index]=min+i; index++; count[i]--; } } }

其实就是建一个新的数组，把每个原数组中出现个个数储存，然后按次序输出

代码实现：先擂台法找到原数组的最大最小值

然后新数组容量就是max-min+1。循环原数组把arr[i]-min当做下标(最小化数组容量)，然后++

然后index归零，遍历新数组，只要新数组元素不为0就把这个数赋值给原数组，然后index++

新数组--

⑧基数排序(待)
⑨ 桶排序(待)

三. 排序算法复杂度及稳定性分析