数据结构常用内排序

发表于 | 分类于 | 次

数据结构常用内排序

  1. 插入排序

    • 直接插入排序：依次将待排序序列中的每一条记录插入到一个已经排好序的序列中，直到全部的记录都排好序。
      在最好情况下，待排序序列为正序，每趟只需与有序序列的最后一个记录的关键码比较。总的比较次数为n-1，因此，时间复杂度为O(n)。在最坏情况下，待排序序列为逆序，第i个记录必须与前i-1个记录的关键码做比较，并且每比较一次就要做一次记录的移动，则移动的次数为 : $\sum_{i=1}^n n= \frac{n(n-1)}{2}$，因此，时间复杂度为$O(n^2)$。 直接插入排序是一种稳定的排序方法

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      void InsertSort(int r[],int len){
          for(int i = 1;i<len;i++){
              int temp  = r[i];
              int j;
              for(j = i-1;j>=0&&r[j]>temp;j--){
                      r[j+1] = r[j];
              }
              r[j+1] = temp;
          }
      }

    • 希尔排序：先将整个待排序记录序列分割成若干个子序列，在子序列内分别进行直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。希尔排序算法的时间性能分析是一个复杂的问题，因为它是所取增量的函数。有人在大量实验的基础上指出，希尔排序的时间性能在$O(n^2)$和O(nlog2n)。希尔排序是一种不稳定的排序方法

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      void ShellSort(int r[],int n){
          for(int d = n/2;d>=1;d = d/2){
              for(int j = d;j<=n;j++){
                  int temp = r[j];
                  int i;
                  for(i = j-d;i>=0&&r[i]>temp;i = i-d){
                      r[i+d] = r[i];
                  }
                  r[i+d] = temp;
              }
          }
      }

  2. 交换排序

    • 起泡排序：两两比较相邻记录的关键码，如果反序则交换，直到没有反序的记录为止。在最好的情况下，待排序的记录为正序时，算法只执行一趟，进行了n-1次关键码的比较，不需要移动记录，时间复杂度为O(n)，在最坏的情况下，待排序的记录为反序，每趟排序在无序序列中只有一个最大的记录被交换到最终位置，故算法执行n-1趟，第i(1<=i<n)趟排序执行了n-i次关键码的比较和n-i次记录的交换，这样，关键码的比较次数为$\sum_{i=1}^{n-1} (n-i)= \frac{n(n-1)}{2}$，因此，时间复杂度为$O(n^2)$。起泡排序是一种稳定的排序方法。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      void Bubble(int r[],int len){
          int exchange = len;
          while(exchange!=0){
              int bound = exchange;
              exchange = 0;
              for(int i = 0;i<bound-1;i++){
                  if(r[i]>r[i+1]){
                      int temp = r[i];
                      r[i] = r[j+1]；
                      r[j+1] = temp;
                      exchange = i+1;
                  }
              }
          }
      }

    • 快速排序：首先选取一个轴值（即比较的基准），将待排序的记录划分为两个独立的两部分，左侧记录的关键码均小于或等于轴值，右侧记录的关键码均大于或等于轴值，然后分别对这两部分重复上述过程。快速排序的平均复杂度为O(nlog2n) 快速排序是一种不稳定的排序方法

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      /*
          快速排序的一次划分算法
       */
      int partition(int r[],int first,int end){
          int i = first,j = end-1;
          while(i<j){
              while(i<j&&r[i]<=r[j]) j--;
              if(i<j){
                  int temp = r[i];
                  r[i] = r[j];
                  r[j] = temp;
                  i++;
              }
              while(i<j&&r[i]<r[j]) i++;
              if(i<j){
                  int temp = r[i];
                  r[i] = r[j];
                  r[j] = temp;
                  j--;
              }
          }
      }
      /*
          快速排序算法
      */
          void quickSort(int r[],int len){
              int pivot = partition(r,0,len-1);
              quickSort(r,0,pivot-1);
              quickSort(r,pivot+1,len-1);
          }

  3. 选择排序

    • 简单选择排序：第i趟排序在待排序序列r[i]~rn中选取关键码最小的记录，并和第i个记录交换作为有序序列的第i个记录。平均复杂度为$O(n^2)$，选择排序是一种不稳定的排序方法

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      void selectSort(int r[],int len){
          for(int i = 0;i<len-1;i++){
              int index = i;
              for(int j = i+1;j<len;j++){
                  if(r[j]>r[index]){
                      index = j;
                  }
              }
              if(index!=i){
                  int temp = r[i];
                  r[i] = r[index];
                  r[index] = temp;
              }
          }
      }

    • 堆排序：首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大值即堆顶记录，然后将该堆顶记录移走，并将剩余的记录再调整成堆，这样又找出了次大的记录。依次类推，直到堆中只有一个记录为止。总的时间复杂度为O(nlog2n)。 堆排序是一种不稳定的排序方法

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      void shift(int r[],int k,int m){
          int i = k,j = 2*i;
          while(j<m){
              if(r[j]<r[j+1]) j++;
              if(r[i]>r[j]) break;
              else{
                  int temp =  r[i];
                  r[i] = r[j];
                  r[j] = temp;
                  i = j;
                  j = 2*i;
              }
          }
      }
      void HeapSort(int r[], int n){
          for(int i = n/2;i>=1;i--){
              shift(r,i,n);
          }
          for(int i = 1;i<n;i++){
              int temp = r[1];
              r[1] = r[n-i+1];
              r[n-i+1] = temp;
              shift(r,1,n-i);
          }
      }