怎么让那2组组内数据有序了

排序算法 平均时间复杂度
冒泡排序 O(n2)
选择排序 O(n2)
插入排序 O(n2)
希尔排序 O(n1.5)
快速排序 O(N*logN)
归并排序 O(N*logN)
堆排序 O(N*logN)
基数排序 O(d(n+r))

图片 1

一. 冒泡排序(BubbleSort)


  1. 核心境想:五个数比较大小,较大的数下沉,较小的数冒起来。

  2. 过程:

  • 正如相邻的多少个数据,若是首个数小,就交流地方。
  • 从后迈入两两对比,一贯到比较最前五个数据。最后最小数被换来到早先的职责,那样第一个细微数的职位就排好了。
  • 接轨重复上述进度,依次将第二.3…n-2个细微数排好职位。
冒泡排序
  1. 平均时间复杂度:O(n2)
  2. java代码落成:

public static void BubbleSort(int [] arr){

        int temp;//临时变量
        for(int i=0; i<arr.length-1; i++){   //表示趟数,一共arr.length-1次。
            for(int j=arr.length-1; j>i; j--){

                if(arr[j] < arr[j-1]){
                    temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }
            }
        }
    }
  1. 优化:
  • 本着难题:
    数量的依次排好之后,冒泡算法依然会一连展开下一轮的相比较,直到arr.length-1遍,后边的可比没有意思的。

  • 方案:
    安装标志位flag,如若爆发了沟通flag设置为true;假若没有交流就安装为false。
    如此那般当一轮相比较甘休后要是flag仍为false,即:这一轮没有暴发沟通,表达数据的各种已经排好,没有须求继续拓展下去。

public static void BubbleSort1(int [] arr){

        int temp;//临时变量
        boolean flag;//是否交换的标志
        for(int i=0; i<arr.length-1; i++){   //表示趟数,一共arr.length-1次。

            flag = false;
            for(int j=arr.length-1; j>i; j--){

                if(arr[j] < arr[j-1]){
                    temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                    flag = true;
                }
            }
            if(!flag) break;
        }
    }
排序算法 平均时间复杂度
冒泡排序 O(n2)
选择排序 O(n2)
插入排序 O(n2)
希尔排序 O(n1.5)
快速排序 O(N*logN)
归并排序 O(N*logN)
堆排序 O(N*logN)
基数排序 O(d(n+r))

二. 拔取排序(SelctionSort)


  1. 基本思维:
    在长短为N的无序数组中,第陆回遍历n-三个数,找到最小的数值与第②个要素互换;
    其次次遍历n-贰个数,找到最小的数值与第二个成分互换;
    。。。
    第n-三次遍历,找到最小的数值与第n-3个因素交流,排序完成。

  2. 过程:

    选用排序

  3. 平均时间复杂度:O(n2)

  4. java代码落实:

public static void select_sort(int array[],int lenth){

      for(int i=0;i<lenth-1;i++){

          int minIndex = i;
          for(int j=i+1;j<lenth;j++){
             if(array[j]<array[minIndex]){
                 minIndex = j;
             }
          }
          if(minIndex != i){
              int temp = array[i];
              array[i] = array[minIndex];
              array[minIndex] = temp;
          }
      }
  }

1. 冒泡排序(Bubble Sort)

  1. 骨干考虑:三个数相比较大小,较大的数下沉,较小的数冒起来。

  2. 过程:

    1. 正如相邻的七个数据,如若第1个数小,就沟通地点。
    2. 从后迈入两两比较,一贯到相比最前多个数据。最后最小数被换来到胚胎的义务,那样第一个细微数的职位就排好了。
    3. 继承重复上述进度,依次将第3.3…n-二个不大数排好岗位。
    ![](https://upload-images.jianshu.io/upload_images/6588416-a8c661a208ad4b66.png)

    冒泡排序
  1. 平均时间复杂度:O(n2)

  2. java代码贯彻:

public static void bubbleSort(int [] arr){

     int temp;//临时变量
     for(int i=0; i<arr.length-1; i++){   //表示趟数,一共arr.length-1次。
         for(int j=arr.length-1; j>i; j--){

             if(arr[j] < arr[j-1]){
                 temp = arr[j];
                 arr[j] = arr[j-1];
                 arr[j-1] = temp;
             }
         }
     }
 }
  1. 优化:
    1. 本着难点:
      多少的各样排好今后,冒泡算法依旧会持续拓展下一轮的比较,直到arr.length-二遍,前面的可比没有意思的。
    2. 方案:
      安装标志位flag,假诺爆发了交流flag设置为true;若是没有交流就安装为false。那样当一轮相比较截止后若是flag仍为false,即:这一轮没有生出交流,表达数据的相继已经排好,没有要求继续开展下去。

public static void bubbleSort1(int [] arr){

   int temp;//临时变量
   boolean flag;//是否交换的标志
   for(int i=0; i<arr.length-1; i++){   //表示趟数,一共arr.length-1次。

       flag = false;
       for(int j=arr.length-1; j>i; j--){

           if(arr[j] < arr[j-1]){
               temp = arr[j];
               arr[j] = arr[j-1];
               arr[j-1] = temp;
               flag = true;
           }
       }
       if(!flag) break;
   }
}
  1. 利口酒排序,也叫定向冒泡排序,是冒泡排序的一种立异。此算法与冒泡排序的两样处在于从低到高然后从高到低,而冒泡排序则仅从低到高去相比较系列里的各样成分。他得以获取比冒泡排序稍微好一些的成效

private static void cocktailSort(int[] arr) {
    int left = 0;
    int right = arr.length-1;
    int temp;
    while (left < right) {
        // 前半轮,将最大元素放到后面
        for (int i = left; i < right; i++) {
            if (arr[i] > arr[i + 1]) {
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
        right--;
        // 后半轮,将最小元素放到前面
        for (int i = right; i > left; i--) {
            if (arr[i] < arr[i - 1]) {
                temp = arr[i];
                arr[i] = arr[i - 1];
                arr[i - 1] = temp;
            }
        }
        left++;
    }
}

三. 插入排序(Insertion Sort)


  1. 中央考虑:
    在要排序的一组数中,假定前n-贰个数已经排好序,以后将第n个数插到前边的雷打不动数列中,使得那n个数也是排好顺序的。如此频仍循环,直到全体排好顺序。

  2. 过程:

    插入排序

相同的场景
  1. 平均时间复杂度:O(n2)

  2. java代码贯彻:

public static void  insert_sort(int array[],int lenth){

      int temp;

      for(int i=0;i<lenth-1;i++){
          for(int j=i+1;j>0;j--){
              if(array[j] < array[j-1]){
                  temp = array[j-1];
                  array[j-1] = array[j];
                  array[j] = temp;
              }else{         //不需要交换
                  break;
              }
          }
      }
  }

2. 采纳排序(Selction Sort)

  1. 大旨考虑:
    在尺寸为N的无序数组中,第6遍遍历n-1个数,找到最小的数值与第3个因素交流;
    其次次遍历n-壹个数,找到最小的数值与第三个要素沟通;
    。。。
    第n-1遍遍历,找到最小的数值与第n-3个要素互换,排序达成。

  2. 过程:

    图片 2

    分选排序

  3. 平均时间复杂度:O(n2)

  4. java代码贯彻:

private static void selectSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

四. 希尔排序(Shell Sort)


  1. 前言:
    数码体系1: 13-17-20-42-28 利用插入排序,13-17-20-28-42. Number of
    swap:1;
    数码序列2: 13-17-20-42-14 利用插入排序,13-14-17-20-42. Number of
    swap:3;
    设若数额系列基本铁板钉钉,使用插入排序会愈来愈高效。

  2. 主导思想:
    在要排序的一组数中,按照某一增量分为若干子种类,并对子连串分别展开插入排序。
    下一场逐步将增量减小,并再次上述进度。直至增量为1,此时多少种类基本有序,最终举行插入排序。

  3. 过程:

    希尔排序

  4. 平均时间复杂度:

  5. java代码落到实处:

  public static void shell_sort(int array[],int lenth){

      int temp = 0;
      int incre = lenth;

      while(true){
          incre = incre/2;

          for(int k = 0;k<incre;k++){    //根据增量分为若干子序列

              for(int i=k+incre;i<lenth;i+=incre){

                  for(int j=i;j>k;j-=incre){
                      if(array[j]<array[j-incre]){
                          temp = array[j-incre];
                          array[j-incre] = array[j];
                          array[j] = temp;
                      }else{
                          break;
                      }
                  }
              }
          }

          if(incre == 1){
              break;
          }
      }
  }

3. 插入排序(Insertion Sort)

  1. 着力考虑:
    在要排序的一组数中,假定前n-3个数已经排好序,以后将第n个数插到日前的逐步数列中,使得那n个数也是排好顺序的。如此频仍循环,直到一切排好顺序。

  2. 过程:

    图片 3

    插入排序

图片 4

一律的现象

  1. 平均时间复杂度:O(n2)

  2. java代码落到实处:

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

五. 快捷排序(Quicksort)


  1. 焦点考虑:(分治)
  • 先从数列中取出二个数作为key值;
  • 将比这么些数小的数全体放在它的左边,大于或等于它的数全部位居它的右手;
  • 对左右五个小数列重复第贰步,直至各区间只有1个数。
  1. 帮助掌握:挖坑填数
  • 初始时 i = 0; j = 9; key=72
    鉴于已经将a[0]中的数保存到key中,能够掌握成在数组a[0]上挖了个坑,可以将别的数据填充到那来。
    从j开端向前找1个比key小的数。当j=8,符合条件,a[0] = a[8] ;
    i++ ;
    将a[8]挖出再填到上三个坑a[0]中。
    诸如此类3个坑a[0]就被消除了,但又摇身一变了贰个新坑a[8],那如何做了?简单,再找数字来填a[8]这个坑。
    这一次从i开首向后找2个超乎key的数,当i=3,符合条件,a[8] = a[3]
    ; j– ;
    将a[3]挖出再填到上2个坑中。

数组:72 - 6 - 57 - 88 - 60 - 42 - 83 - 73 - 48 - 85
      0   1   2    3    4    5    6    7    8    9
  • 此时 i = 3; j = 7; key=72
    再另行上边的步骤,先从后迈入找,再在此之前向后找。
    从j开首向前找,当j=5,符合条件,将a[5]挖出填到上三个坑中,a[3]
    = a[5]; i++;

    从i初始向后找,当i=5时,由于i==j退出。
    此时,i = j = 5,而a[5]恰好又是上次挖的坑,由此将key填入a[5]。

数组:48 - 6 - 57 - 88 - 60 - 42 - 83 - 73 - 88 - 85
      0   1   2    3    4    5    6    7    8    9
  • 可以看出a[5]目前的数字都低于它,a[5]前面的数字都超出它。由此再对a[0…4]和a[6…9]这个子区间重复上述手续就可以了。

数组:48 - 6 - 57 - 42 - 60 - 72 - 83 - 73 - 88 - 85
      0   1   2    3    4    5    6    7    8    9
  1. 平均时间复杂度:O(N*logN)

  2. 代码完毕:

public static void quickSort(int a[],int l,int r){
        if(l>=r)
          return;

        int i = l; int j = r; int key = a[l];//选择第一个数为key

        while(i<j){

            while(i<j && a[j]>=key)//从右向左找第一个小于key的值
                j--;
            if(i<j){
                a[i] = a[j];
                i++;
            }

            while(i<j && a[i]<key)//从左向右找第一个大于key的值
                i++;

            if(i<j){
                a[j] = a[i];
                j--;
            }
        }
        //i == j
        a[i] = key;
        quickSort(a, l, i-1);//递归调用
        quickSort(a, i+1, r);//递归调用
    }

key值的取舍可以有各个方式,例如中间数恐怕专断数,分别会对算法的复杂度暴发区其他熏陶。

4. 希尔排序(Shell Sort)

  1. 前言:
    数量连串1: 13-17-20-42-28 利用插入排序,13-17-20-28-42. Number of
    swap:1;
    数码系列2: 13-17-20-42-14 利用插入排序,13-14-17-20-42. Number of
    swap:3;
    假若数据系列基本铁钉铁铆,使用插入排序会愈加高效。

  2. 着力考虑:
    在要排序的一组数中,根据某一增量分为若干子体系,并对子体系分别进行插入排序。
    下一场逐步将增量减小,并再一次上述进程。直至增量为1,此时多少连串基本平稳,最终举行插入排序。

  3. 过程:

    图片 5

    希尔排序

  1. java代码落实:

private static void shellSort(int[] arr) {
    int n = arr.length;
    int h = 1;
    while (h < n / 3) {
        //1  4  13  40  121...
        h = 3 * h + 1;
    }
    while (h >= 1) {
        for (int i = h; i < n; i++) {
            for (int j = i; j >= h; j -= h) {
                if (arr[j] < arr[j - h]) {
                    int temp = arr[j];
                    arr[j] = arr[j - h];
                    arr[j - h] = temp;
                }
            }
        }
        h = h / 3;
    }
}

六. 归并排序(Merge Sort)


  1. 主题考虑:参考
    归并排序是白手起家在联合操作上的一种有效的排序算法。该算法是应用分治法的壹个尤其优良的使用。
    率先考虑下怎么将3个不变数列合并。这一个十分简单,只要从相比二个数列的率先个数,什么人小就先取何人,取了后就在对应数列中去除这一个数。然后再拓展比较,即便有数列为空,那直接将另3个数列的数量依次取出即可。

//将有序数组a[]和b[]合并到c[]中
void MemeryArray(int a[], int n, int b[], int m, int c[])
{
    int i, j, k;

    i = j = k = 0;
    while (i < n && j < m)
    {
        if (a[i] < b[j])
            c[k++] = a[i++];
        else
            c[k++] = b[j++]; 
    }

    while (i < n)
        c[k++] = a[i++];

    while (j < m)
        c[k++] = b[j++];
}

消除了地点的会合有序数列难点,再来看归并排序,其的基本思路就是将数组分成2组A,B,若是那2组组内的数额都以平稳的,那么就足以很有益的将那2组数据举办排序。怎么着让那2组组内数据有序了?
能够将A,B组各自再分为2组。依次类推,当分出来的小组只有1个数据时,可以认为那么些小组组内已经达成了平稳,然后再统一相邻的三个小组就足以了。那样经过先递归的解释数列再统一数列就完了了归并排序。

  1. 过程:

    归并排序

  2. 平均时间复杂度:O(NlogN)
    归并排序的作用是相比高的,设数列长为N,将数列分开成小数列一共要logN步,每步都以贰个联合有序数列的长河,时间复杂度可以记为O(N),故一共为O(N*logN)。

  3. 代码已毕:

 public static void merge_sort(int a[],int first,int last,int temp[]){

     if(first < last){
         int middle = (first + last)/2;
         merge_sort(a,first,middle,temp);//左半部分排好序
         merge_sort(a,middle+1,last,temp);//右半部分排好序
         mergeArray(a,first,middle,last,temp); //合并左右部分
     }
 }

 //合并 :将两个序列a[first-middle],a[middle+1-end]合并
 public static void mergeArray(int a[],int first,int middle,int end,int temp[]){     
     int i = first;
     int m = middle;
     int j = middle+1;
     int n = end;
     int k = 0; 
     while(i<=m && j<=n){
         if(a[i] <= a[j]){
             temp[k] = a[i];
             k++;
             i++;
         }else{
             temp[k] = a[j];
             k++;
             j++;
         }
     }   
     while(i<=m){
         temp[k] = a[i];
         k++;
         i++;
     }   
     while(j<=n){
         temp[k] = a[j];
         k++;
         j++; 
     }

     for(int ii=0;ii<k;ii++){
         a[first + ii] = temp[ii];
     }
 }

5. 火速排序(Quick Sort)

  1. 着力考虑:

    1. 先从数列中取出多个数作为基准数。
    2. 分区进程,将比那一个数大的数全松开它的左侧,小于或等于它的数全放手它的左边。
    3. 再对左右间隔重复第叁步,直到各区间唯有一个数。
  2. 过程:
    纵然高效排序称为分治法,但分治法那多个字分明不大概很好的不外乎快捷排序的任何步骤。由此小编的对便捷排序作了一发的验证:挖坑填数+分治法:
    先来看实例吧,定义下边再交由(最好能用本人的话来总括定义,那样对贯彻代码会有赞助)。

以五个数组作为示范,取区间第1个数为基准数。

0 1 2 3 4 5 6 7 8 9
72 6 57 88 60 42 83 73 48 85

初始时,i = 0; j = 9; X = a[i] = 72
是因为已经将a[0]中的数保存到X中,可以知道成在数组a[0]上挖了个坑,可以将其余数据填充到那来。

从j开头向前找三个比X小或等于X的数。当j=8,符合条件,将a[8]挖出再填到上贰个坑a[0]中。a[0]=a[8];
i++;
那样贰个坑a[0]就被化解了,但又形成了多少个新坑a[8],那如何是好了?简单,再找数字来填a[8]本条坑。本次从i初始向后找3个大于X的数,当i=3,符合条件,将a[3]挖出再填到上2个坑中a[8]=a[3];
j–;

数组变为:

0 1 2 3 4 5 6 7 8 9
48 6 57 88 60 42 83 73 88 85

i = 3; j = 7; X=72
再重新上边的手续,先从后迈入找,再从前向后找。
从j开头向前找,当j=5,符合条件,将a[5]挖出填到上一个坑中,a[3] =
a[5]; i++;
从i伊始向后找,当i=5时,由于i==j退出。
此时,i = j = 5,而a[5]正好又是上次挖的坑,因而将X填入a[5]。

数组变为:

0 1 2 3 4 5 6 7 8 9
48 6 57 42 60 72 83 73 88 85

可以看来a[5]前边的数字都低于它,a[5]末端的数字都不止它。由此再对a[0…4]和a[6…9]那一个子区间再度上述手续就可以了。

  1. 总结:

    1. i =L; j = 景逸SUV; 将基准数挖出善变第三个坑a[i]。
    2. j–由后迈入找比它小的数,找到后挖出此数填前贰个坑a[i]中。
    3. i++由前向后找比它大的数,找到后也挖出此数填到前多个坑a[j]中。
    4. 再重新执行2,3二步,直到i==j,将基准数填入a[i]中。
  2. 平均时间复杂度:O(NlogN)

  3. java代码贯彻:

private static void quickSort(int[] arr, int left, int right) {
    if (left >= right) {
        return;
    }
    int i = left;
    int j = right;
    //选择第一个数为key
    int key = arr[left];
    while (i < j) {
        //从右向左找第一个小于key的值
        while (i < j && arr[j] >= key) {
            j--;
        }
        if (i < j) {
            arr[i] = arr[j];
            i++;
        }
        //从左向右找第一个大于key的值
        while (i < j && arr[i] < key) {
            i++;
        }
        if (i < j) {
            arr[j] = arr[i];
            j--;
        }
    }
    arr[i] = key;
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}

七. 堆排序(HeapSort)


  1. 基本考虑:

  2. ** 图示:** (88,85,83,73,72,60,57,48,42,6)

Heap Sort
  1. 平均时间复杂度:O(NlogN)
    由于每一次重复回涨堆的时日复杂度为O(logN),共N –
    一遍重复上升堆操作,再加上前边建立堆时N /
    3次向下调整,每回调整时间复杂度也为O(logN)。三回操作时间相加如故O(N *
    logN)。

  2. java代码贯彻:

//构建最小堆
public static void MakeMinHeap(int a[], int n){
    for(int i=(n-1)/2 ; i>=0 ; i--){
        MinHeapFixdown(a,i,n);
    }
}
  //从i节点开始调整,n为节点总数 从0开始计算 i节点的子节点为 2*i+1, 2*i+2  
  public static void MinHeapFixdown(int a[],int i,int n){

      int j = 2*i+1; //子节点
      int temp = 0;

      while(j<n){
          //在左右子节点中寻找最小的
          if(j+1<n && a[j+1]<a[j]){   
              j++;
          }

          if(a[i] <= a[j])
              break;

          //较大节点下移
          temp = a[i];
          a[i] = a[j];
          a[j] = temp;

          i = j;
          j = 2*i+1;
      }
  }

 public static void MinHeap_Sort(int a[],int n){
     int temp = 0;
     MakeMinHeap(a,n);

     for(int i=n-1;i>0;i--){
         temp = a[0];
         a[0] = a[i];
         a[i] = temp; 
         MinHeapFixdown(a,0,i);
     }   
 }

6. 归并排序(Merge Sort)

  1. 核心情维:
    归并排序是赤手空拳在统一操作上的一种有效的排序算法。该算法是行使分治法的3个万分优秀的使用。
    首先考虑下哪些将一个静止数列合并。那几个格外简单,只要从相比3个数列的第3个数,哪个人小就先取什么人,取了后就在相应数列中剔除这么些数。然后再举办相比,倘若有数列为空,那直接将另2个数列的数量依次取出即可。
    化解了上边的集合有序数列难题,再来看归并排序,其的基本思路就是将数组分成2组A,B,假如那2组组内的数码都以不变的,那么就可以很有益的将那2组数据举行排序。怎样让那2组组内数据有序了?
    可以将A,B组各自再分为2组。依次类推,当分出来的小组只有一个数据时,可以认为那些小组组内已经达到了一如既往,然后再统一相邻的3个小组就足以了。这样经过先递归的表明数列,再统一数列就做到了归并排序。

  2. 过程:

    图片 6

    归并排序

![](https://upload-images.jianshu.io/upload_images/6588416-d60eec343771d5f2.png)

自顶向下的归并排序中归并结果的轨迹



![](https://upload-images.jianshu.io/upload_images/6588416-44561353f283ed12.png)

自顶向下的归并排序的调用轨迹
  1. 平均时间复杂度:O(NlogN)
    归并排序的效用是相比较高的,设数列长为N,将数列分开成小数列一共要logN步,每步都是二个合并有序数列的进度,时间复杂度可以记为O(N),故一共为O(N*logN)。

  2. java代码完结:

private static int[] temp;

private static void mergeSort(int[] arr) {
    temp = new int[arr.length];
    sort(arr, 0, arr.length - 1);
}

private static void sort(int[] arr, int left, int right) {
    if (left >= right) {
        return;
    }
    int mid = left + (right - left) / 2;
    sort(arr, left, mid);
    sort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

private static void merge(int[] arr, int left, int mid, int right) {
    int i = left;
    int j = mid + 1;
    for (int k = left; k <= right; k++) {
        temp[k] = arr[k];
    }
    for (int k = left; k <= right; k++) {
        if (i > mid) {
            arr[k] = temp[j++];
        } else if (j > right) {
            arr[k] = temp[i++];
        } else if (temp[j] < temp[i]) {
            arr[k] = temp[j++];
        } else {
            arr[k] = temp[i++];
        }
    }
}

八. 基数排序(RadixSort)


7. 堆排序(Heap Sort)

  1. 主导思维:

    1. 结构三个堆有序的数组并使最大要素位于数组的起初(次大的成分在紧邻)而非构造函数甘休的末段。
    2. 将堆中的最大因素删除,然后放入堆减少后数组中空出的任务
  2. 过程:

    图片 7

    堆排序的轨道

![](https://upload-images.jianshu.io/upload_images/6588416-7d755ad154b1da9b.png)

堆的构造(左)和下沉排序(右)
  1. 平均时间复杂度:O(NlogN)
    是因为每一次重复恢复生机堆的小时复杂度为O(logN),共N –
    一次重复回涨堆操作,再增进前面建立堆时N /
    二次向下调整,每一次调整时间复杂度也为O(logN)。一遍操作时间相加依旧O(N *
    logN)。

  2. java代码完结:

private static void heapSort(int[] arr) {
    int n = arr.length;
    for (int k = n / 2; k >= 1; k--) {
        sink(arr, k, n);
    }
    while (n > 1) {
        swap(arr, 1, n--);
        sink(arr, 1, n);
    }
}

private static void sink(int[] arr, int k, int n) {
    while (2 * k <= n) {
        int j = 2 * k;
        if (j < n && arr[j - 1] < arr[j]) {
            j++;
        }
        if (arr[k - 1] >= arr[j - 1]) {
            break;
        }
        swap(arr, k, j);
        k = j;
    }
}

private static void swap(int[] arr, int i, int j) {
    int temp = arr[i - 1];
    arr[i - 1] = arr[j - 1];
    arr[j - 1] = temp;
}
BinSort
  1. 主导思想:
    BinSort想法相当不难,首先成立数组A[MaxValue];然后将各种数放到对应的任务上(例如17放在下标17的数组地点);最终遍历数组,即为排序后的结果。

  2. ** 图示:**

BinSort
  1. ** 问题:**
    当序列中存在较大值时,BinSort 的排序方法会浪费多量的长空开发。

8. 基数排序(Radix Sort)

RadixSort
  1. 大旨绪维:
    基数排序是在BinSort的底蕴上,通过基数的限制来压缩空间的费用。

  2. 过程:

    过程1

过程2


(1)首先确定基数为10,数组的长度也就是10.每个数34都会在这10个数中寻找自己的位置。  
(2)不同于BinSort会直接将数34放在数组的下标34处,基数排序是将34分开为3和4,第一轮排序根据最末位放在数组的下标4处,第二轮排序根据倒数第二位放在数组的下标3处,然后遍历数组即可。
  1. java代码落到实处:

public static void RadixSort(int A[],int temp[],int n,int k,int r,int cnt[]){

      //A:原数组
      //temp:临时数组
      //n:序列的数字个数
      //k:最大的位数2
      //r:基数10
      //cnt:存储bin[i]的个数

      for(int i=0 , rtok=1; i<k ; i++ ,rtok = rtok*r){

          //初始化
          for(int j=0;j<r;j++){
              cnt[j] = 0;
          }
          //计算每个箱子的数字个数
          for(int j=0;j<n;j++){
              cnt[(A[j]/rtok)%r]++;
          }
          //cnt[j]的个数修改为前j个箱子一共有几个数字
          for(int j=1;j<r;j++){
              cnt[j] = cnt[j-1] + cnt[j];
          }
          for(int j = n-1;j>=0;j--){      //重点理解
              cnt[(A[j]/rtok)%r]--;
              temp[cnt[(A[j]/rtok)%r]] = A[j];
          }
          for(int j=0;j<n;j++){
              A[j] = temp[j];
          }
      }
  }

[2015-08-31]

BinSort
  1. 骨干思想:
    BinSort想法极度不难,首先创造数组A[MaxValue];然后将种种数放到相应的任务上(例如1伍个人于下标17的数组地方);最终遍历数组,即为排序后的结果。

  2. 图示:

    图片 8

    BinSort

  3. 问题:当种类中设有较大值时,BinSort
    的排序方法会浪费大量的空间开发。

RadixSort
  1. 骨干思维:
    基数排序是在BinSort的底蕴上,通过基数的限量来裁减空间的支出。
  2. 过程:

    图片 9

    过程1

![](https://upload-images.jianshu.io/upload_images/6588416-b9d44a95c0697897.png)

过程2

(1)首先分明基数为10,数组的尺寸也等于10.各个数34都会在那拾2个数中寻觅自个儿的职位。
(2)差距于BinSort会直接将数34放在数组的下标34处,基数排序是将三24分别为3和4,第一批次排序依据最最后一位放在数组的下标4处,第②轮排序依据尾数第二个人放在数组的下标3处,然后遍历数组即可。

  1. java代码落成:

private static void radixSort(int[] arr, int r, int d) {
    int len = arr.length;
    int[] temp = new int[len];

    for (int i = 0, rate = 1; i < d; i++) {
        // 重置count数组,开始统计下一个关键字
        int[] count = new int[r + 1];
        // 将arr中的元素完全复制到temp数组中
        for (int j = 0; j < len; j++) {
            temp[j] = arr[j];
        }
        // 计算每个待排序数据的子关键字
        for (int j = 0; j < len; j++) {
            int num = (temp[j] / rate) % 10;
            count[num + 1]++;
        }
        // 记录每个桶的元素在整个数组的下标
        for (int j = 0; j < r; j++) {
            count[j + 1] += count[j];
        }
        // 按子关键字对指定的数据进行排序
        for (int j = 0; j < len; j++) {
            int num = (temp[j] / rate) % 10;
            arr[count[num]++] = temp[j];
        }
        rate *= 10;
    }
}

9. 记数排序(Count Sort)

  1. 思想:
    计数排序假如n个输入成分中的每一个都以在0到k区间内的八个整数,其中k是为有些整数。
    对每2个输入成分x,分明小于x的要素个数。利用这一音信,就可以直接把x放在它在输出数组中的地方上。
    比方系列中小于成分x的个数为a,则平昔把x放到第a+二个地点上。
    只要种类中小于等于成分x的个数为b,则一贯把x放到第b个岗位上。
    由于下标是从0开端的,而记录的b至少是1,全体在程序中应有需求减1
    当存在多少个一律的因素时要做适当的调动,因为不恐怕把拥有的要素放到同3个职位上。

  2. 平均时间复杂度:O(n+k)

  3. java代码落成:

private static void countSort(int[] arr, int max) {
    int len = arr.length;
    int[] temp = new int[len];
    int[] count = new int[max + 2];
    for (int i = 0; i < len; i++) {
        temp[i] = arr[i];
    }
    for (int i : arr) {
        count[i + 1]++;
    }
    for (int i = 0; i < max + 1; i++) {
        count[i + 1] += count[i];
    }
    for (int i = 0; i < len; i++) {
        arr[count[temp[i]]++] = temp[i];
    }
}

相关文章