排序 - 图1

选择排序

①简单选择排序

简单选择排序思路：在未排序的序列中选出最小的元素和序列的首位元素交换，接下来在剩下的未排序序列中再选出最小元素与序列的第二位元素交换，依此类推，最后形成从小到大的已排序序列。

  1. // 简单选择排序，时间复杂度：O（n2）
  2. public static void choiceSort(int[] a){
  3.     int len = a.length;
  4.     for (int i=0;i<len;i++){
  5.         int index = i;
  6.         // 寻找最小元素
  7.         for (int j=i+1;j<len;j++){
  8.             if (a[index]>a[j]){
  9.                 //记录最小元素下标
  10.                 index = j;
  11.             }
  12.        }
  13.        // 交换
  14.        int temp = a[index];
  15.        a[index] = a[i];
  16.        a[i]=temp;
  17.     }
  18. }

②堆排序*

堆排序思路：把最大元素和当前堆中数组的最后一个元素交换位置，并且不删除它，那么就可以得到一个从尾到头的递减序列，从正向来看就是一个递增序列，这就是堆排序。

利用最大堆（或者最小堆）输出堆顶元素，即最大值（或者最小值），将剩余元素重新生成最大堆（或者最小堆），继续输出堆顶元素，重复此过程，直到全部元素都已输出，得到的输出元素序列即为有序序列。

  1. 首先将一个无序的序列生成一个最大堆，如（a）不需要输出堆顶元素，只需对换堆顶与堆最后一个元素的位置即可如（b）。此时最后一个元素99一定是递增序列的最后一个元素，且在对的位置。（c）是调整后形成的新的最大堆。要注意99已被排除在最大堆外，即在调整的时候，堆中元素个数-1.结束第一轮调整后，再次将当前堆中最后一个元素22与堆顶元素对换，如（d），再继续调整成新的最大堆······如此循环，直到堆中只剩一个元素，即可停止，得到一个从小到大的序列。

image.png

  1. /*堆排序，时间复杂度O（nlogn）*/
  2. void PercDown(int a[],int p,int n)
  3. {
  4. /*将n个元素的数组中以a[p]为根的子堆调整为最大堆*/
  5.     int Parent,Child; 
  6.     int x;
  7.     x=a[p];/*取出根结点存放的值*/
  8.     for(Parent=p;(Parent*2+1)<n;Parent=Child)
  9.     {
  10.         Child=Parent*2+1;
  11.         if((Child!=n-1)&&(a[Child]<a[Child+1]))
  12.             Child++;/*Child指向左右子结点的较大者*/
  13.         if(x>=a[Child]) 
  14.             break;/*找到了合适位置*/
  15.         else /*下滤x*/
  16.             a[Parent]=a[Child];
  17.     }
  18.     a[Parent]=x;
  19. }
  20. void HeapSort(ElementType a[],int n)
  21. {/*堆排序*/
  22.     int i;
  23.     for(i=n/2-1;i>=0;i--)/*建立最大堆*/
  24.         PercDown(a,i,n);
  25.     for(i=n-1;i>0;i--)
  26.     {/*删除最大堆顶*/
  27.         Swap(a[0],a[i]);
  28.         PercDown(a,0,i);
  29.     }
  30. }

插入排序

①简单插入排序

将待排序的一组序列分为已排好序的和未排序的两个部分；初始状态时，已排序序列仅包含第一个元素，未排序序列中的元素为除去第一个元素以外的N-1 个元素；此后将未排序序列中的元素逐一插入到已排序的序列中。如此往复，经N-1 次插入后，未排序序列元素个数为0，则排序完成。

插入排序思路：每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左侧数组依然有序。

  1.     // 插入排序，时间复杂度：O（n2）
  2.     public static void insertSort(int[] a){
  3.         int len = a.length;
  4.         for (int i=0;i<len;i++){
  5.             //  取出未排序序列中的第一个元素，即右侧第一个
  6.             int temp = a[i];
  7.             int j;
  8.             for (j=i;j>0&&a[j-1]>temp;j--){
  9.                 // 比未排序大的元素右移
  10.                 a[j] = a[j-1];
  11.             }
  12.             // 放进合适位置
  13.             a[j] = temp;
  14.         }
  15.     }

②希尔排序*

  1. 将待排序的一组元素按一定间隔分为若干个序列，分别进行插入排序。开 始时设置的“间隔”较大，在每轮排序中将间隔逐步减小，直到“间隔”为1，也就是 最后一步是进行简单插入排序。

希尔排序思路：希尔排序使用插入排序对间隔 h 的序列进行排序。通过不断减小 h，最后令 h=1，就可以使得整个数组是有序的。

待排序列：{44，12，59，36，62，43，94，7，35，52，85}

增量序列：{5，3，1}

image.png

  1. void ShellSort(int a[],int n)
  2. {
  3. /*希尔排序-用Sedgewick增量序列*/
  4.     int Si,d,p,i;
  5.     int temp;
  6.     int Sedgewick[]={929,505,209,109,41,19,5,1,0}/*这里只列出小部分增量*/
  7.     for(Si=0;Sedgewick[Si]>=n;Si++);/*初始的增量Sedgewick[Si]不能超过待排序列长度*/
  8.     for(d=Sedgewick[Si];d>0;d=Sedgewick[++Si])
  9.     { 
  10.         for(p=d;p<n;p++)
  11.         {/*插入排序*/
  12.             temp=a[p];
  13.             for(i=p;i>=d&&a[i-d]>temp;i-=d)
  14.                 a[i]=a[i-d];
  15.             a[i]=temp;
  16.         }
  17.     } 
  18. }

交换排序

①冒泡排序

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的 顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复 地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

冒泡排序思路：从左到右不断交换相邻逆序的元素，在一轮的循环之后，可以让未排序的最大元素上浮到右侧。在一轮循环中，如果没有发生交换，就说明数组已经是有序的，此时可以直接退出。

  1. // 冒泡排序，时间复杂度：O（n2） 
  2. // 1. 从当前元素起，向后依次比较每一对相邻元素，若逆序则交换 
  3. // 2. 对所有元素均重复以上步骤，直至最后一个元素 
  5.     public void bubbleSort(int[] a) {
  6.         int len = a.length;
  7.         for (int i=0;i<len-1;i++){
  8.             // 外循环为排序趟数，len个数进行len-1趟
  9.             for (int j=0;j<len-1-i;j++){
  10.                 // 内循环为每趟比较的次数，第i趟比较len-i次
  11.                 if (a[j]>a[j+1]){
  12.                     // 相邻元素比较，若逆序则交换（升序为左大于右，逆序反之）
  13.                     int temp = a[j];
  14.                     a[j]=a[j+1];
  15.                     a[j+1]=temp;
  16.                 }
  17.             }
  18.         }
  19.     }
  21. // 添加一个状态变量对冒泡排序进行优化
  22.     public void bubbleSort(int[] a) {
  23.         int len = a.length;
  24.         boolean isSorted = false;
  25.         for (int i=len-1;i>0 && !isSorted ;i--){
  26.             //!isSorted 条件，当 isSorted=true 时说明是有序的，则不需要再执行了
  27.             isSorted = true; //初始时认为是有序的
  28.             for (int j=0;j<i;j++){
  29.                 // 内循环为每趟比较的次数，第i趟比较len-i次
  30.                 if (a[j]>a[j+1]){
  31.                     isSorted = false; //存在逆序，则是无序的
  32.                     int temp = a[j];
  33.                     a[j]=a[j+1];
  34.                     a[j+1]=temp;
  35.                 }
  36.             }
  37.         }
  38.     }

②快速排序*

快速排序思路：快速排序通过一个切分元素将数组分为两个子数组，左子数组小于等于切分元素，右子数组大于等于切分元素，将这两个子数组排序也就将整个数组排序了。

将未排序元素根据一个作为基准的“主元”（Pivot）分为两个子序列，其中一个子序列的记录大于主元，而另一个子序列的记录小于主元，然后递归地堆这两个子序列用类似的方法进行排序。

image.png

  1.     public void quickSort(int[] a){
  2.         fastSort(a,0,a.length-1);
  3.     }
  4.     private void fastSort(int[] a,int start ,int end){
  5.         if (start>end){
  6.             return;
  7.         }
  8.         int p = partition(a,start,end);
  9.         fastSort(a,start,p-1);
  10.         fastSort(a,p+1,end);
  11.     }
  12.     private int partition(int[] a, int start, int end){
  13.         int pivot = a[start];
  14.         while (start<end) {
  15.             while (start < end && a[end] >= pivot) {
  16.                 end--;
  17.             }
  18.             a[start] = a[end];
  19.             while (start < end && a[start] <= pivot) {
  20.                 start++;
  21.             }
  22.             a[end] = a[start];
  23.         }
  24.         a[start] = pivot;
  25.         return start;
  26.     }

归并排序*

归并排序的思想：将数组分成两部分，分别进行排序，然后归并起来。

将大小为N的序列看成N个长度为1的子序列，接下来将相邻子序列两两进行归并操作，形成N/2（+1）个长度为2（或者1）的有序子序列；然后再继续进行相邻子序列两两进行归并操作，如此一直循环，直到剩下一个长度为N的序列，则该序列为原序列完成排序后的结果。

image.png

  1. public void sort(int[] arr){
  2.     sort(arr,0,arr.length-1);
  3. }
  5. private void sort(int[] arr,int l,int r){
  6.     if(l>=r){
  7.         return;
  8.     }
  9.     int mid = (r-l)/2+l;
  10.     //对 [l,mid] 进行排序
  11.     sort(arr,l,mid);
  12.     //对 [mid+1,r] 进行排序
  13.     sort(arr,mid+1,r);
  14.     //合并这两个有序数组
  15.     merge(arr,l,mid,r);
  16. }
  18. //合并两个有序数组
  19. //[l,mid]
  20. //[mid+1,r]
  21. private void merge(int[] arr,int l,int mid,int r){
  22.     int[] nums = new int[r-l+1];
  23.     int index=0;
  24.     int i=l;
  25.     int j=mid+1;
  26.     while(i<=mid && j<=r){
  27.         if(arr[i]<arr[j]){
  28.             nums[index++] = arr[i++];
  29.         }else{
  30.             nums[index++] = arr[j++];
  31.         }
  32.     }
  33.     while(i<=mid){
  34.         nums[index++]=arr[i++];
  35.     }
  36.     while(j<=r){  
  37.         nums[index++]=arr[j++];
  38.     }
  40.     index=0;
  41.     for(int k=l;k<=r;k++){
  42.         arr[k] = nums[index++];
  43.     }
  44. }

基数排序

①桶排序

  1. 如果已知N个关键字的取值范围是0到M-1之间，而M比N小得多，则桶排序算法将为关键字的每个可能取值建立一个“桶”，即建立M个桶；在扫描N个关键字时，将每个关键字放入相应的桶中，然后按桶的顺序收集一遍就自然有序了。

②基数排序

  1. 基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶 子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元 素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时 间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排 序法的效率高于其它的稳定性排序法。