十大排序演算法–多圖預警

  • 2019 年 10 月 3 日
  • 筆記
 

??????

 

 

???????

Θ(n^2)

????

  • ????

 

enter description here

enter description here

 

  • ??

    ??????????????????????????????????????????????????????????????????????????????????????????????????

  • ??

    // ?????????  public static void exc(int[] a,int i, int j) {          if (a[i]!=a[j]) {              a[i]^=a[j];              a[j]^=a[i];              a[i]^=a[j];          }      }  // ????  public static void insertSort(int[] a, int n) {          for (int i = 1; i < n; i++) {              for (int j = i; j>0&&a[j-1]>a[j]; j--) {                  exc(a, j, j-1);              }          }      }

  • ??

    ?????

    • ??? n×n/4 ????n×n/4 ???
    • ??? n-1 ????0???
    • ??? n×n/2 ???? n×n/2 ??

    ???

    ? ??????????????????? O(n)?????????????????C???quickSort???

????

  • ????

    enter description here

  • ??

    ???????????????????????????????

  • ??

    public static void bubbleSort(int[] a, int n) {          boolean flag = true;          for (int i = 0; i < n-1&&flag; i++) {              flag = false;              for (int j = 0; j < n-i-1; j++) {                  if (a[j]>a[j+1]) {                      exc(a, j, j+1);                      flag=true;                  }              }          }      }

  • ??

    ??????

    • ??????????????????????????????
    • ?????? ??????????????????????O(n^2)?

???

??????????????? flag???????????????????????????????????????????????

????

  • ????

    selectSort

  • ??

    ???????????????????????????????????????????????????????……

  • ??

    // ???????      public static void selectSort(int[] a,int n) {          for (int i = 0; i < n; i++) {              int min=i;              for (int j = i+1; j < n; j++) {                  if(a[min]>a[j]){                      min = j;                  }              }              if (min!=i) {                  exc(a, i, min);              }            }      }

  • ??

    ??????

    • ?????? (n-1)+(n-2)+…+1= n(n-1)/2

    • ?????? n

    ??:

    • ????????????????????????????
    • ???????????

?????????

Θ(nlog?n)

????

  • ????

    shellSort

  • ??

    ???????????????????????????????????????????????????????????????????????????????????

    ??????????????????????????????????step????????????????????????????????????h???????????????????h=1????????????????

  • ??

    // 6. ????      public static void shellSort(int[] a, int n) {          int h =1;          while (h<n/3) {              // ?? 1,4,13,40...              h = h*3+1;          }          while (h>=1) {              for (int i = h; i < n; i++) {                  for(int j=i;j>=h&&a[j-h]>a[j];j-=h){                      exc(a, j, j-h);                  }              }              h/=3;          }      }

  • ??

    ???????????O(n^2)???
    ??–????????????????????????
    ???????????????????

????

  • ????

    quickSort

  • ??

    ???????? Divide and Conquer ????????????????????????????????????????????????????????????? ? ???????

  • ???

    1. ???????????????????“??”?pivot??

    2. ?????????????????????????????????????????????????????????????????????????????????????

    3. ??????????????????????????????????????

    ??????????????????????????????????

  • ??

    // ????      public static int partition(int[] a,int l,int h) {          int mid = l+((h-l)>>1);          int pivot = a[mid];          exc(a, l, mid);          int i = l;          int j = h+1;          while (true) {              while (a[++i]<pivot) {                  if(i==h) break;              }              while (a[--j]>pivot) {                  if(j==l) break;              }              if (i>=j) {                  break;              }              exc(a, i, j);          }          exc(a, l, j);          return j;      }      public static void quickSort(int[] a, int n) {          quickSort(a, 0, n-1);        }      // ????      public static void quickSort(int[] a, int lo, int h) {          if (lo>=h) {              return;          }          int j = partition(a, lo, h);          quickSort(a, lo, j-1);          quickSort(a, j+1, h);      }

  • ??

    ?????????????O(n^2)????????? O(n logn)????????????????????????????????????????????

????

  • ????

    mergeSort

  • ??

    ?????:

    • ???????????????????
    • ?????????????????????????????????
    • ?????????????????????????????????? ???????
  • ??

    // ???? ??      public static void merge(int[] a, int low, int mid, int high) {          // ?????          int i = low;          int j = mid + 1;          int k = 0;          int[] a2 = new int[high - low + 1];          while (i <= mid && j <= high) {              if (a[i] < a[j]) {                  a2[k] = a[i];                  i++;                  k++;              } else {                  a2[k] = a[j];                  j++;                  k++;              }          }          while (i <= mid) {              a2[k] = a[i];              i++;              k++;          }          while (j <= high) {              a2[k] = a[j];              j++;              k++;          }          for (k = 0, i = low; i <= high; k++, i++) {              a[i] = a2[k];          }      }    public static void mergeSort(int[] a, int n) {          mergeSort(a, 0, n - 1);      }  // ???? ??  public static void mergeSort(int[] a, int low, int high) {          if (low >= high)              return;          int mid = (high + low) / 2;          mergeSort(a, low, mid);          mergeSort(a, mid + 1, high);          merge(a, low, mid, high);      }

  • ??

    ?????????????????????????? O(nlogn),???????????????????????????????? O(n)

???

  • ????

    heapSort

  • ??

    ??????????????????

    heap

    ????????????????????????????k???????????(k+1)/2-1???????????????2k+1?2k+2?????????????????????????

    ??? ?????????????????????????????k(=1,2,3…)??????????????? sink(??) ????

  • ??

    // ??  public static void buildHeap(int[] a, int n) {          for (int i = n / 2; i >= 0; i--) {              heapify(a, n - 1, i);          }      }  // ??  public static void heapify(int[] a, int n, int i) {          while (true) {              int maxPos = i;              if (i * 2 + 1 <= n && a[i] < a[2 * i + 1]) {                  maxPos = i * 2 + 1;              }              if (i * 2 + 2 <= n && a[maxPos] < a[i * 2 + 2]) {                  maxPos = i * 2 + 2;              }              if (i == maxPos) {                  break;              }              exc(a, i, maxPos);              i = maxPos;          }      }    public static void heapSort(int[] a, int n) {          buildHeap(a, n);          int k = n - 1;          while (k > 0) {              // ?????????1,2,3...???????              exc(a, 0, k);              --k;              heapify(a, k, 0);          }      }

  • ??

    • ????????? O(nlogn)??????????
    • ???
      1. ?????
      2. ?????????????????????
      3. ????????(???)

???????????

Θ(n)

????

  • ????

    countSort

  • ??

    ?????????????C??? C ??i?????????A????i?????????????C ??A????????????

    tips:?????????????????????????????????????????????????????????????

  • ??

    // ?????      public static void countSort(int[] a, int n) {          int max = a[0];          for (int i = 0; i < n; i++) {              if (a[i] > max) {                  max = a[i];              }          }          int[] c = new int[max + 1];          int indexArray = 0;          for (int i = 0; i < n; i++) {              c[a[i]]++;          }          for (int i = 0; i <= max; i++) {              if (c[i] != 0) {                  a[indexArray] = i;                  c[i]--;                  indexArray++;              }          }      }

???

  • ????

    bucket

  • ??

    ??????????????[min,max]?????????min?max????????????????????[min,max]???n???n??????n????????????????????????????????????????????(?????)????????????

  • ??

    public static void bucketSort(int[] a, int n, int bucketSize) {          int max = a[0];          int min = a[1];          for (int v : a) {              if (v > max) {                  max = v;              } else if (v < min) {                  min = v;              }          }            // ????          int bucketCount = (max - min) / bucketSize + 1;          int bucket[][] = new int[bucketCount][bucketSize];          int indexArr[] = new int[bucketCount];          // ??????????          for (int v : a) {              int j = (v - min) / bucketSize;              if (indexArr[j] == bucket[j].length) {                  ensureCapacity(bucket, j);              }              bucket[j][indexArr[j]++] = v;          }          // ?????      	// ????????????          int k = 0;          for (int i = 0; i < bucketCount; i++) {              if (indexArr[i] == 0) {                  continue;              }              quickSort(bucket[i], indexArr[i]);              for (int j = 0; j < indexArr[i]; j++) {                  a[k++] = bucket[i][j];              }          }        }        // ????      private static void ensureCapacity(int[][] bucket, int j) {          int[] tempArr = bucket[j];          int[] newArr = new int[tempArr.length * 2];          for (int k = 0; k < tempArr.length; k++) {              newArr[k] = tempArr[k];          }          bucket[j] = newArr;      }

  • ??

    ??????????????????????????? ?m? ,??? ????n?????????? K??????????????????????????????????

    • ????? O(N+C)???C=N*(logN-logK)??????? O(N+K)
    • ????????????? N????M??????????????????? 0-750??????????????????????

????

  • ????

    radixSort

  • ??

    ????????????????????????????????

    ???????? LSD (Least sgnificant digital) ? MSD (Most sgnificant digital) ??????????????(LSD)??????????????????????????????????????????????

  • ??

    /**       *       * @param x  ??????       * @param d  ?d?       * @param dg ????       * @return ???????       */      public static int getDigit(int x, int d, int[] dg) {          return (x / dg[d - 1] % 10);      }        /**       *       * @param a ?????       * @param n ????       */      public static void radixSort(int[] a, int n) {          // ????          int max = 0;          int j = 0, i = 0;          // ?????          final int radix = 10;          for (int val : a) {              if (val > max) {                  max = val;              }          }          // ?????          int N;          if (max == 0) {              N = 1;          } else {              N = (int) Math.log10(max) + 1;          }          // ??????          int dg[] = new int[N + 1];          for (i = 1, dg[0] = 1; i < N + 1; i++) {              dg[i] = 10 * dg[i - 1];          }          // ????          int bucket[][] = new int[radix][n];          int indexArr[] = new int[radix];          for (int d = 1; d <= N; d++) {              for (int var : a) {                  j = getDigit(var, d, dg);                  bucket[j][indexArr[j]++] = var;              }              int count = 0;              for (i = 0; i < radix; i++) {                  if (indexArr[i] != 0) {                      for (int k = 0; k < indexArr[i]; k++) {                          a[count++] = bucket[i][k];                      }                      indexArr[i] = 0;                  }              }          }      }

  • ??

    ?????? O(k*n)???????O(n),??????????????????????????

????

  1. ??????????????????????????????? O(nlogn) ????????????????????????? n! ???????? ????? ??????????????????? nlogn?

  2. ?????????????????????????????????????????????????????????

    ?????????????????????????????????????????????

    ??????????????? ?