排序

• 1. 排序的概念

  • 1.1 时间复杂度分析
  • 1.2 空间复杂度分析
  • 1.3 术语

• 2. 计数排序

• 3. 插入排序

  • 3.1 直接插入排序
  • 3.2 二路插入排序
  • 3.3 折半插入排序
  • 3.4 希尔排序（缩小增量排序）

• 4. 交换排序

  • 4.1 冒泡排序

    • 4.1.1 冒泡排序-稳定
    • 4.1.2 双向冒泡排序
    • 4.1.3 梳排序

  • 4.2 快速排序(分区排序）-不稳定

• 3. 选择排序

  • 3.1 简单选择排序
  • 3.2 堆排序

• 4. 二路归并排序

• 5.分配排序

  • 5.1 桶排序
  • 5.2 基数排序

1. 排序的概念

1.1 时间复杂度分析

排序码比较次数估计、元素移动次数估计

1.2 空间复杂度分析

基本储存空间为n，考虑额外的储存空间。 原地排序为$O(1)O(1)$

1.3 术语

• 排序码：或关键字，作为排序比较的依据。
• 稳定性：相等排序码的不同元素在排序前后相对位置是否发生颠倒。
• 原地排序：排序仅在$O(1)O(1)$个储存空间帮助排序，原数组中调整顺序。
• 内排序：排序过程均在内存的排序方法。
• 外排序：排序过程频繁进行内、外存交换，或文件排序。

2. 计数排序

• 有序序列中，一个元素所处位置取决于具有更小排序码的元素个数。
• 增加元素计数域Count，存放有序序列中该元素前面的元素数目。最多需要做$n(n-1)\mathrm{/}2n(n-1)/2$次排序码比较。

//CountSort
const int len=10;
int count[len]{0};
for(int i=0;i<len;i++)
	for(int j=i+1;j<len;j++)
    	if(arr[j]<arr[i]) count[i]++;
        else count[j]++;
for(int i=0;i<len;i++){
	int j=i;
    while(count[j]!=i) j=count[j];//找计数为i的第j个元素
    if(i!=j){
    	swap(arr[i],arr[j]);
        count[j]=count[i];
    }
}

3. 插入排序

3.1 直接插入排序

• 将待排序列按排序码插入有序序列(序列左为有序表，右为无序表)
• 排序码比较次数$KCN=O(n)\sim O(n^2)KCN\; =\; O(n)\backslash sim\; O(n^2)$
• 元素移动次数$RMN=O(1)\sim O(n^2)RMN\; =\; O(1)\backslash sim\; O(n^2)$
• 时间复杂度$O(n^2)O(n^2)$ 空间复杂度$O(1)O(1)$

void InsertSort(SeqList& L){
  for(int i=0;i<L.n-1;i++)
    if(L.data[i]>L.data[i+1]){
      DataType temp = L.data[i+1];//缓存元素，腾空位移动元素
      for(int j=i;j>=0 && temp<L.data[j];j--)
        L.data[j+1] = L.data[j];//比较并不断移动元素，把大值后移
      L.data[j+1] = temp;//找到合适位置插入缓存元素
    }
}

3.2 二路插入排序

• 构造与L.data等长辅助数组t[n], n=L.n, t[n-1]=L.data[0]，小值初始化;
• 指针first指向t[n-1]，final指向-1;
• 依次比较, L.data[i]<t[n-1] 插入左边t[n-2]，否则插入右边t[0];

void DoubleInsertSort(SeqList& L){
  const int n = L.n;
  int t[n]{0};
  t[n-1]=L.data[0];
  int first = n-1, final = -1;
  
  for(int i=0;i<L.n;i++){
    if(L.data[i]<t[n-1]){
      for(int j=first;j<n-1;j++){
        if(L.data[i]>t[j]) t[j-1] = t[j];//从first开始找，更小的后移
        else break;
        t[j-1] = L.data[i];first--;
     }
     else{
       for(int j=final;j>=0;j--)
         if(L.data[j]<t[j]) t[j+1]=t[j];
         else break;
         t[j+1] = L.data[i];final++;
     }
  }
  for(int i=0,j=first;j<n;i++,j++) L.data[i] = t[j];
  for(int j=0; j<=final;i++;j++) L.data[i] = t[j];
}   

3.3 折半插入排序

• 与直接插入排序不同在于，在有序区寻找插入位置采用折半查找，而非顺序查找。
• 比较次序为折半查找

$KCN=lo{g}_2(n!)\approx nlo{g}_{2}n\approx nlognKCN=log\_2(n!)\backslash approx\; nlog\_2n\; \backslash approx\; nlogn$

void BinaryInsertSort(SeqList& L){
  for(int i=1;i<L.n;i++){
    if(L.data[i]<L.data[i-1]){
      DataType temp = L.data[i];
      int low = 0, high = i-1;
      while(low<=high){
        int mid = (low+high)/2;
        if(temp<L.data[mid]){
          for(int j=high;j>=mid;j--)
            L.data[j+1]=L.data[j];//中间值以后的元素，从最大值开始后移
          high = mid-1;
        }
        else low = mid+1;
      }
      L.data[low] = temp;
    }
  }

3.4 希尔排序（缩小增量排序）

• 全部元素划分为gap个子序列，每趟处理一个gap增量
• 每个gap分别进行插入排序
• 缩小增量gap，重复划分排序，直至其为1
• 效率高，空间复杂度$O(1)O(1)$，不稳定

void insertSort_gap(SeqList& L, int start, int gap){
  for(int i=start+gap;i<L.n;i+=gap){
    if(L.data[i-gap]>L.data[i]){
      DataType temp = L.data[i];
      int j=i;
      do{
        L.data[j] = L.data[j-gap];
        j-=gap;
      }while(j-gap>0&&L.data[j-gap]>temp);
      L.data[j] = temp;
    }
  }
  
  void ShellSort(SeqList& L, int delta[], int m){
    for(int i=m-1;i>=0;i--){
      int gap = delta[i];
      for(int start=0;start<gap;start++)
        insertSort_gap(L,start,gap);
    }//delta[0]=1停止迭代
  }

4. 交换排序

• 逆序则交换

4.1 冒泡排序

4.1.1 冒泡排序-稳定

• 相邻元素互相比较，较大值右移--冒泡。
• 时间复杂度$O(n^2)O(n^2)$， 空间复杂度$O(1)O(1)$

每次循环将最大值交换到了最右端。

void BuddleSort(SeqList& L){
  for(int i=0;i<L.n-2;i++){
    int exchange = 0;
    for(int j=L.n-1;j>=i+1;j--)
      if(L.data[j-1]>L.data[j]){
        Swap(L,j-1,j);
        exchenge = 1;
      }
    if(!exchange) return;
  }
}

4.1.2 双向冒泡排序

• 第一趟把排序码最大的对象放在序列最后
• 第二趟把排序码最小的对象放在序列最前
• bool exchange 记录当前一趟是否有元素交换，没有交换则退出
• 鸡尾酒排序（用high记录交换元素的位置，为0退出）

void shakeSort(SeqList& L){
  int low=0,high=L.n-1;
  bool Exchange = true;
  while(low<high&&Exchange){
    Exchange = false;//j=low;
    for(int i= low;i<high;i++)
      if(L.data[i]>L.data[i+1]){
        Swap(L,i,i+1);Exchange = true;//j=i;
      }
    high--;//high=j;
    for(int i=high;i>low;i--)
      if(L.data[i-1]>L.data[i]){
        Swap(L,i,i-1);Exchange = true;//j=i;
      }
    low++;//low=j;
  }
}
      

4.1.3 梳排序

• 冒泡排序前对数据进行预处理，将一些大的元素放在数组尾部，大幅降低两两交换的次数
• 取因子$s=1.3s=1.3$，确定元素间隔$n\mathrm{/}s,n\mathrm{/}{s}^2,\mathrm{.}\mathrm{.}\mathrm{.},n\mathrm{/}{s}^{p}n/s,\; n/s^2,\; ...,\; n/s^p$取整
• $n\mathrm{/}{s}^p=2->p=lo{g}_s(n\mathrm{/}2)n/s^p\; =\; 2\; ->\; p\; =\; log\_s(n/2)$ 预处理复杂度$O(nlo{g}_s(n))O(nlog\_s(n))$

void condSort(SeqList& L){
  int step = L.n, count=0;
  while((step=(int)(step/1.3))>1){
    for(int j=L.n-1;j>=step;j--){
      int k=j-step;
      if(L.data[j]<L.data[k]){
        Swal(L,j,k);count++;}
    }
    bool Exchange = true;
    for(int i=0;i<L.n-1&&Exchange;i++){
      count=0;
      for(j=L.n-1;Exchange=false;j>i;--j)
        if(L.data[j]<L.data[j-1]){
          Swap(L,j,j-1);Exchange = true;count++;}
    }
  }

4.2 快速排序(分区排序）-不稳定

• 一趟划分法： 任选一元素作为中间值，将整个元素与中间值进行对比，根据元素排序码大小放在中间值左右两边。
• 三种实现方式：
• 两边检测指针相向交替检查和移动元素
• 两边检测指针相向检查，发现逆序即交换
• 一个检测指针一遍检查，发现逆序交换

int Partition_1(SeqList& L, low,high){
  int i=low, j=high;
  DataType pivot = L.data[low];
  while(i!=j){
    while(i<j&&L.data[j]>=pivot) j--;//反向查找，比基准元素小退出循环，更新j值；
    if(i<j) L.data[i++]=L.data[j];//将小值移动到低端
    while(i<j&&L.data[i]<=pivot) i++;//正向查找，比基准元素大推出循环，更新i值；
    if(i<j) L.data[j--] = L.data[i];//将大值移动到高端
  }
  L.data[i] = pivot;//找到基准元素对应的位置i；
  return i;
}

3. 选择排序

3.1 简单选择排序

• 选择左端值，将较小值与左端值进行交换。
• 时间复杂度$O(n^2)O(n^2)$， 空间复杂度$O(1)O(1)$

每次循环将最小值交换至最左端。

int len = sizeof(arr) / sizeof(int);
for(int i=0;i<len;i++)
        for(int j=i+1;j<len;j++)
            if(arr[i]>arr[j]) swap(arr[i],arr[j]);

3.2 堆排序

4. 二路归并排序

5.分配排序

5.1 桶排序

5.2 基数排序