数据结构排序方法总结

Posted: September 17, 2019

Status: Completed

Were equations, pictures or diagrams not properly rendered, please refresh the page. If the problem persists, you can contact me.

内部排序：

一、插入排序（每次将一个待排序的记录按关键字大小插入到前面已经排好序的子序列）

1.直接插入排序（稳定）（边比较边移动）（并不是每次排序元素都在最后的位置）

查找出 L( i ) 在 L[1…i-1] 中的插入位置 k；
将 L[k…i-1] 中的所有元素全部后移一个位置；
将 L( i ) 复制到 L( k )；

#include <stdio.h>
#include <stdlib.h>

void InsertSort(int A[],int n){ //不带哨兵
  int i,j;
  int temp;
  for(i=1;i<n;i++){ //从头到尾，依次使用固定的三步
    temp = A[i]; //被检测的元素，对应L（i）
    for(j=i;j>0;j--){
      if(A[j-1] > temp){
        A[j] = A[j-1]; //既比较大小，又往后移位
      }
      else{
        break;
      }
    }
    A[j] = temp; //对应第三步
  }
}

void InsertSort1(int A[],int n) { //带哨兵
  int i,j;
  for(i=2;i<n;i++){
    A[0] = A[i]; //哨兵存储
    for(j=i-1;A[j]>A[0];j--){
      A[j+1] = A[j];
    }
    A[j+1] = A[0];
  }
}

void  PrintArray(int A[],int n) {
  int i=0;
  for(i;i<n;i++){
    printf("%d\n",A[i]);
  }
}

int main(int argc, char const *argv[]) {
  int A[5] = {2,3,1,5,99}; //不带哨兵
  int B[6] = {0,2,3,1,5,99}; //带哨兵
  // PrintArray(A,5);
  // InsertSort(A,5);
  // PrintArray(A,5);
  InsertSort(B,6);
  PrintArray(B,6);
  return 0;
}

空间效率：O（1）；
时间效率：O（n^2）；
稳定性：直接插入排序是一个稳定的排序方法；
适用性：顺序存储和链式存储（需要从前往后查找指定元素）都行；

2.折半插入排序（稳定）（并不是每次排序元素都在最后的位置）

折半查找出 L( i ) 在 L[1…i-1] 中的插入位置 k；
将 L[k…i-1] 中的所有元素全部后移一个位置；
将 L( i ) 复制到 L( k )；

#include <stdio.h>
#include <stdlib.h>

void InsertSort(int A[],int n){
  int i,j,low,mid,high;
  for(i=2;i<n;i++){
    A[0] = A[i];
    low=0,high=i-1; //设置折半查找的范围
    while(low<=high){
      mid = (high+low)/2;
      if(A[mid] >A[0]){
        high = mid -1; //查找左半子表
      }
      else{
        low = mid+1;
      }
    }
    for(j=i-1;j>high;j--){
      A[j+1] = A[j];
    }
    A[high+1] = A[0];
  }
}


void  PrintArray(int A[],int n) {
  int i=0;
  for(i;i<n;i++){
    printf("%d\n",A[i]);
  }
}

int main(int argc, char const *argv[]) {
  int B[6] = {0,2,3,1,5,99}; //带哨兵
  // PrintArray(A,5);
  // InsertSort(A,5);
  PrintArray(B,6);
  InsertSort(B,6);
  PrintArray(B,6);
  return 0;
}

空间效率：O（1）；
时间效率：O（n^2），比较次数与待排序表初始状态无关，仅仅取决于表中的元素个数n，但移动次数依旧依赖于排序表的初始状态；
稳定性：折半插入排序是一个稳定的排序方法；
适用性：顺序存储，数据量较小的表；

3.希尔排序（不稳定）（并不是每次排序元素都在最后的位置）

先将待排序表分割成若干形如 L[ i, i + d, i + 2d ,…, i + kd] 的特殊子表；
分别进行直接插入排序；
再对总体进行插入排序；
目前，还没有得到最好的增量序列；

#include <stdio.h>
#include <stdlib.h>

void ShellSort(int A[],int n){
  int i,j,dk;
  for(dk=n/2;dk>=1;dk=dk/2){ //希尔所使用的增量序列，最后一个增量为1
    for(i=dk+1;i<=n;++i){ //这个是从加了dk的地方开始，然后一个一个地加1，这样的话可以找到所有分组，各组进行直插
      if(A[i]<A[i-dk]){
        A[0] = A[i];  //然后在希尔的时候已经是在内部了，本身就没有这个判断，已经不需要哨兵的作用，没有起加强的效果
        for(j=i-dk;j>0&&A[0]<A[j];j-=dk){ //各组进行直插
          A[j+dk] = A[j]; //移动
        }
        A[j+dk] = A[0];
    }
  }
}
}

void  PrintArray(int A[],int n) {
  int i=0;
  for(i;i<n;i++){
    printf("%d\n",A[i]);
  }
}

int main(int argc, char const *argv[]) {
  int A[5] = {2,3,1,5,99}; //不带哨兵
  int B[6] = {0,2,3,1,5,99}; //带哨兵
  // PrintArray(A,5);
  // InsertSort(A,5);
  // PrintArray(A,5);
  ShellSort(B,6);
  PrintArray(B,6);
  return 0;
}

空间效率：O（1）；
时间效率：难以定论，最坏情况是O（n^2），一般情况是O（n^1.3）；
稳定性：折半插入排序是一个不稳定的排序方法；
适用性：顺序存储；

二、交换排序（根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的为之）

1.冒泡排序（稳定）（每次排序都有一个元素都在最终的位置）

一趟冒泡
- 假设待排序表长为n，从后往前遍历（或者从前往后）
- 两两比较相邻元素的值
- 直到序列比完
下一趟冒泡
- 下一趟冒泡时，前一趟确定的最小元素不再参与比较
最多n-1趟冒泡就能完全排好

void BubbleSort(int A[],int n) {
  int i,j;
  int temp; //用来交换
  int flag; //用来判断有没有发生交换
  for(i=0;i<n;i++){
    flag = 0;
    for(j=n-1;j>i;j--){ //这个到底是从后往前还是从前往后是有区别的，一个是将小的冒泡一个是将大的沉底,这里选择冒泡
      if(A[j-1]>A[j]){  //第i次冒泡需要进行n-i次比较
        temp = A[j-1];  //这儿就是移动的三次
        A[j-1] = A[j];
        A[j] = temp;
        flag = 1;
      }
    }
    if(flag == 0){
      return;
    }
    }
}

空间效率：O（1）
时间效率：O（n^2）
稳定性：冒泡排序是一种稳定的排序方法

2.快速排序（不稳定，考的比较多，是对冒泡排序的改进，基本思想基于分治法）（每趟都会将一个元素（基准元素）放在其最终的位置上）

在待排序表L[1…n]中任取一个元素pivot作为基准
通过一趟排序将待排序表划分为独立的两部分L[1…k-1]和L[k+1…n]
L[1…k-1]中所有元素都小于pivot，L[k+1…n]中所有元素都大于等于pivot
那么pivot就放在了它的最终为之L[k]，这个过程称为一趟快排
递归分别对两个字表重复过程
划分操作决定了该算法的性能，一般用严奶奶的方法

#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0

typedef struct Node{
  int data;
  struct Node *next;
}Node,*Stack;

typedef struct LinkStack{
  Node* top; //栈顶指针
  int count; //元素个数
}LinkStack;

LinkStack InitStack(){
  LinkStack stack;
  stack.top = NULL;
  stack.count = 0;
  return stack;
}

void Push(LinkStack* stack,int x){
  Node* s;
  s = (Node*)malloc(sizeof(Node));
  s->next = stack->top;
  s->data = x;
  stack->top = s;
  stack->count++;
}

void Pop(LinkStack* stack){
  Node* s;
  s = stack->top;
  stack->top = stack->top->next;
  free(s);
  stack->count--;
}


int isEmpty(LinkStack stack)
{
    if (stack.count == 0)
    {
        return TRUE;
    }
    else
        return FALSE;
}


int Partition(int A[],int low,int high){ //划分关键就是要找到基准最终的位置，然后划分
  int pivot = A[low]; //将表中第一个元素设置为枢轴值，从而对表进行划分
  while(low < high){
    while (low<high&&A[high]>=pivot) { //比基准大的这一趟就不用管，下一个，我还能打！
      --high;
    }
    A[low] = A[high]; //这个就是比基准小的，滚到左端去
    while (low<high&&A[low]<=pivot) { //比基准小的这一趟就不用管，下一个
      ++low;
    }
    A[high] = A[low]; //这个就是比基准大的，滚到右端去
  }
  A[high] = pivot; //把基准放到它的最终位置
  return high; //这个时候high与low已经相等了，无所谓返回哪个，都是k
}

void QuickSort(int A[],int low,int high){
  if(low<high){
    int pivotpos = Partition(A,low,high);
    QuickSort(A,low,pivotpos-1);
    QuickSort(A,pivotpos+1,high);
  }
}

void QuickSort1(int A[],int low,int high){ //这个地方使用非递归版本
  if(low>=high){
    return;
  }
  LinkStack S = InitStack();
  Push(&S,low);
  Push(&S,high);

  while (isEmpty(S) == 0) {
    high = S.top->data;
    Pop(&S);
    low = S.top->data;
    Pop(&S);
    if(low < high){
      int pivotpos = Partition(A,low,high);
      //左区间
      Push(&S,low);
      Push(&S,pivotpos-1);
      //右区间
      Push(&S,pivotpos+1);
      Push(&S,high);
    }
  }
}

void  PrintArray(int A[],int n) {
  int i=0;
  for(i;i<=n;i++){
    printf("%d\n",A[i]);
  }
}

int main(int argc, char const *argv[]) {
  int A[] = {2, 2, 32, 12, 60, 2, 5, 72};
  QuickSort(A,0,7);
  PrintArray(A,7);
  return 0;
}

空间效率：由于快排是递归的，需要借助递归工作栈，容量和递归调用的最大深度一致，O（log2n）
时间效率：与划分是否对称有关，O（nlog2n），是内部排序中平均性能最牛逼的那个,所以
稳定性：快速排序是不稳定的排序算法
知道为啥快排对于基本有序时效果反而差些吗？就是因为基准的选择嘛，一旦你按严奶奶基准来，那么划分的序列就不是很均匀，反而会降低效率

三、选择排序

1.简单选择排序（不稳定）（每一趟确定一个元素的最终位置）

假设排序表为L[1…n]
第i趟，从L[i…n]中选择关键字最小的元素与L(i)交换
每一趟确定一个元素的最终位置
n-1趟可以使整个排序表有序，最后一个元素不用管

#include <stdio.h>
#include <stdlib.h>


void SelectSort(int A[], int n){
  int i,j,min;
  int temp;
  for(i=0;i<n-1;i++){
    min = i; //记录最小元素的位置
    for(j=i+1;j<n;j++){ //找到这一趟后面的最小关键字，并记录位置
      if(A[j] < A[min]){
        min = j;
      }
      if(min!=i){ //就算后面存在与现在i相同的关键字大小也无所谓，赋值后下一趟就能解决问题
        temp = A[i];
        A[i] = A[min];
        A[min] = temp;
      }
    }
  }
}
void  PrintArray(int A[],int n) {
  int i=0;
  for(i;i<n;i++){
    printf("%d\n",A[i]);
  }
}

int main(int argc, char const *argv[]) {
  int A[5] = {2,3,1,5,99};
  SelectSort(A,5);
  PrintArray(A,5);
  return 0;
}

空间效率：O(1)
时间效率：O(n^2)，与初始序列的排列无关
稳定性：不稳定

2.堆排序（不稳定）

在排序过程中，将L[1…n]视为一棵完全二叉树，然后利用完全二叉树双亲结点和孩子结点之间的内在关系，在当前无序区选择关键字最大或者最小的元素（特点）
堆的定义（经常被用来实现优先级队列）：
- 小根堆：L(i) <= L(2i) && L(i) <= L(2i + 1)
- 大根堆：L(i) => L(2i) && L(i) => L(2i + 1)
- 1 <= i <= 向下取整[i/2]
对定向下取整[i/2]为根的子树进行筛选，使其成为堆，依次完成剩下的根结点，完成类似操作

#include <stdio.h>
#include <stdlib.h>


void AdjustDown(int A[],int k,int n){ //这个k就是每次开始调整的点
  A[0] = A[k]; //A[0]暂存
  for(int i=2*k;i<=n;i*=2){ //这个循环就是为了反复调整：调整之后不是堆结构的情况
    if(i<n&&A[i]<A[i+1]){
      i++;  //将i指向相同根下值较大的那个结点，如果这个判断错误，自然最开始的子结点大咯
    }
    if(A[0] >= A[i]) break; //这就不用换了
    else{
      A[k] = A[i];
      k = i;
    }
  }
  A[k] = A[0];
}

void AdjustUp(int A[],int k){ //这个k既是向上调整的结点，也是堆的元素个数
  A[0] = A[k];
  int i = k/2; //找到双亲结点
  while(i>0&&A[i]<A[0]){
    A[k] = A[i];
    k = i;
    i = k/2;
  }
  A[k] = A[0];
}

void BuildMaxHeap(int A[],int n){
  for(int i=n;i>0;i--){
    AdjustUp(A,i);
  }
}

void  PrintArray(int A[],int n) {
  int i=1;
  for(i;i<=n;i++){
    printf("%d\n",A[i]);
  }
}

void HeapSort(int A[],int n){
  int temp;
  BuildMaxHeap(A,n); //先把堆建起来！！！
  for(int i=n-1;i>1;i--){ //把已经弄好的堆顶元素弄出来，交换到排序表需要的位置，完成物理变化，而不是逻辑变化
    temp = A[i];
    A[i] = A[1];
    A[1] = temp;
    AdjustDown(A,1,i-1); //交换元素以后重新建立堆结构
  }
}

int main(int argc, char const *argv[]) {
  int A[9] = {0,53,17,78,9,45,65,87,32};
  // HeapSort(A,9);
  BuildMaxHeap(A,8);
  PrintArray(A,8);
  return 0;
}

空间效率：O(1)
时间效率：一直都是O(nlog2n)，与初始序列的排列无关
稳定性：不稳定

四、归并排序与基数排序

1.归并排序（将两个或两个以上的有序表组合成一个新的有序表）（稳定）

假定待排序表含有n个记录，将其视为n个有序的字表，每个子表长度为1
两两归并，得到向下取整[n/2]个长度为2或者1的有序表
重复上述过程
直到合并成一个长度为n的有序表为止

#include <stdio.h>
#include <stdlib.h>

void Merge(int A[],int low,int mid,int high){
  int i,j,k;\
  int *temp = (int *)malloc((high+1)*sizeof(int)); //temp是用来作为临时存储的辅助数组
  for(k=low;k<=high;k++){
    temp[k] = A[k]; //将A中所有元素都复制到辅助数组中
  }
  for(i=low, j=mid+1, k=i;i<=mid&&j<=high;k++){ //比较辅助数组左右两段的元素
    if(temp[i] <= temp[j]){ //将辅助数组中较小值复制到A中
      A[k] = temp[i++];
    }
    else
      A[k] = temp[j++];
  }
  while (j<=high) { //如果第一个表没有检测完，也就是第一个表长一些，继续复制回A数组剩下的位置
    A[k++] = temp[j++];
  }
  while (i<=mid) { //如果第二个表没有检测完，也就是第二个表长一些，继续复制回A数组剩下的位置
    A[k++] = temp[i++];
  }
}

void MergeSort(int A[],int low,int high){
  if(low < high){
    int mid = (low+high)/2;
    MergeSort(A,low,mid);
    MergeSort(A,mid+1,high);
    Merge(A,low,mid,high);
  }
}

void  PrintArray(int A[],int n) {
  int i=0;
  for(i;i<=n;i++){
    printf("%d\n",A[i]);
  }
}

int main(int argc, char const *argv[]) {
  int A[5] = {2,3,1,5,99};
  MergeSort(A,0,4);
  PrintArray(A,4);
  return 0;
}

空间效率：O(n)
时间效率：O(nlog2n)
稳定性：二路归并是稳定的排序方法

2.基数排序（特别的排序方法，基于关键字各位的大小排序）（按位排序，当然稳定）

我们直接用实例理解，这里采用最低位优先
假设原来有一串数值如下所示：

73, 22, 93, 43, 55, 14, 28, 65, 39, 81

首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：

箱数

0

1 81

2 22

3 73 93 43

4 14

5 55 65

6

7

8 28

9 39
接下来将这些桶子中的数值重新串接起来，成为以下的数列：

81, 22, 73, 93, 43, 14, 55, 65, 28, 39

接着再进行一次分配，这次是根据十位数来分配：

箱数

0

1 14

2 22 28

3 39

4 43

5 55

6 65

7 73

8 81

9 93
接下来将这些桶子中的数值重新串接起来，成为以下的数列：

14, 22, 28, 39, 43, 55, 65, 73, 81, 93

这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。

LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好。MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。

#include<stdio.h>

#define MAX 20 //最大排序的数组元素个数
#define BASE 10

void print(int *a, int n) {  //输出数组函数
  int i;
  for (i = 0; i < n; i++) {
    printf("%d\t", a[i]);
  }
}

void radixsort(int *a, int n) {
  int i, b[MAX], m = a[0], exp = 1; //b数组应该是用来暂时存储的

  for (i = 1; i < n; i++) {
    if (a[i] > m) {
      m = a[i]; //m是这个数组序列中的最大值
    }
  }

  while (m / exp > 0) { //这个exp应该是判断的基数位置，刚开始是1，后来是10，再然后100......
    int bucket[BASE] = { 0 }; //bucket用来统计0-9这些基数存在个数数组

    for (i = 0; i < n; i++) {
      bucket[(a[i] / exp) % BASE]++; //每个数字对应基数的数目，从高位开始
    }

    for (i = 1; i < BASE; i++) {
      bucket[i] += bucket[i - 1]; //0-9的对应的篮子中，是包含其前面所有种类之和（包含自己）
    }

    for (i = n - 1; i >= 0; i--) {
      b[--bucket[(a[i] / exp) % BASE]] = a[i]; //按照前面的基数排序嘛，而且我们不是统计了每个基数的个数嘛，那么轮下来，刚好能够按照大小排序，毕竟基数已经排好序了，我们按个数对应就好
    }

    for (i = 0; i < n; i++) {
      a[i] = b[i]; //将排好序的值重新赋值回去
    }

    exp *= BASE;
  }
}

int main() {
  int arr[MAX]; //被排序的数组
  int i, n;

  printf("Enter total elements (n <= %d) : ", MAX);
  scanf("%d", &n);
  n = n < MAX ? n : MAX; //用这个来判断数组的元素个数，不超过20个，

  printf("Enter %d Elements : ", n); //保存输入的数组元素
  for (i = 0; i < n; i++) {
    scanf("%d", &arr[i]);
  }

  printf("\nARRAY  : ");
  print(&arr[0], n); //输出刚开始的数组刨铣

  radixsort(&arr[0], n);

  printf("\nSORTED : ");
  print(&arr[0], n);
  printf("\n");

  return 0;
}

空间效率：O(r)
时间效率：O(d(n+r))
稳定性：稳定

外部排序（前面的内部排序都是在内存中进行的，实际应用中可能需要对大文件进行排序，需要在将存在外存中的文件一部分一部分地调入内存中，然后再进行排序）：

一、外部排序的基本方法

磁盘文件排序（直接存取设备，由于读写操作的机械动作所需时间远超内存运算时间，时间代价主要考虑访问磁盘的次数，通常采用归并排序算法）
1. 根据内存缓冲区的大小，将外存上含n个记录的文件分成若干长度为h的子文件，依次读入内存并利用有效的内部排序方法对他们进行排序，将排序后得到的有序子文件重新写回外存，这些有序子文件通常称之为归并段或者顺串
2. 对这些归并段进行逐趟归并，使归并段从小到大，直到完成整个有序文件
3. 外部排序的总时间 = 内部排序的总时间 + 外存信息读写的时间 + 内部归并所需时间（若要提高外部排序速度，应该尽量减少I/O次数）
4. 增大归并路数，可以减少归并趟数，也就可以减少总的磁盘I/O次数
磁带文件排序（顺序存取设备）

二、多路平衡归并与败者树

原因
1. 增加归并路数m可以减少归并趟数
2. 但归并路数的增加，会使内部归并的时间增加
3. 内部归并时，m个元素中选取关键字最小的记录需要比较m-1次（这话我暂时还不太理解）
4. 每趟归并n个元素需要做(n-1)(m-1)次比较
5. S(n-1)(m-1) = 向上取整(logmr)(n-1)(m-1) = 向上取整(log2r)(n-1)(m-1)/向上取整(log2m)(这一段随m增大而增大)，可能会抵消收益，不能直接使用内部归并排序算法

败者树（当做一棵完全二叉树，所以可以用数组表示咯，可以利用这种树的性质）

将新进入选择树的结点与其父结点进行比赛：将败者存放在父结点中；而胜者再与上一级的父结点比较。
比赛沿着到根结点的路径不断进行，直到ls[1]处。把败者存放在结点ls[1]中，胜者存放在ls[0]中。

代码：

int loserTree[K];               /* 存储中间节点值，下标0处存储冠军节点 */
int leaves[K+1];                /* 从下标1开始存储叶子节点值，下标0处存储一个最小值节点 */
       
void adjust(int i)
{
    int parent=(i+K-1)/2;      /* 求出父节点的下标 */
    while(parent>0)
    {
        if(leaves[i]>leaves[loserTree[parent]])
        {
            int temp=loserTree[parent];
            loserTree[parent]=i;
            /* i指向的是优胜者 */
            i= temp;
        }
        parent = parent / 2;
    }
    loserTree[0]=i;
}
       
void initLoserTree()
{
    int i;
    for(i=1;i<K+1;i++)
        scanf("%d",&leaves[i]);
    leaves[0]=MIN;
    for(int i=0;i<K;i++)
        loserTree[i]=0;
    for(int i=K;i>0;i--)
        adjust(i);
}

归并路数并不是越大越好，增大路数时，相应的需要增加输入缓冲区的个数，如果可用内存空间不够，每个输入缓冲区的容量肯定要变小，那么交换数据的次数也会增大

三、置换-选择排序（之所以需要的原因是之前的内部排序方法会得到长度都相同的初始归并段，所以需要探索这个方法生成新的归并段，这也是由败者树实现的）

从待排序文件FI中输入w个记录到工作区WA
从内存工作区WA中选出关键字最小的记录，记为MINIMAX
将MINIMAX记录输出到FO初始归并段中
若FI没有读完，则从FI输入下一个记录到WA
从WA中所有关键字比MINIMAX记录的关键字大的记录中选出最小的关键字，作为新的MINIMAX
重复3-5，直到选不出新的MINIMAX记录为止，得到一个初始归并段，输出结束标志到FO中
重复2-6，直到WA为空

四、最佳归并树（现在已经得到长度不等的归并段了，讨论如何组织初始归并段，从而使I/O顺序最少）

m路归并排序可以用一棵m叉树描述
是一棵只有度0和度m的严格m叉树
叶结点到根结点的路径长度代表在归并过程中的归并趟数
带权路径长度WPL是总读记录数，所有I/O总数是2×WPL
为了减少WPL，自然就用到了哈弗曼树的思想：这也就产生了我们所需的最佳归并树
另外（很重要）：如果初始归并段不足以构成一棵严格的m叉树时，需要添加长度为0的虚段，至于添加多少个虚段呢：
- n0 = (m-1)nm + 1
- (n0 - 1)%(m - 1) = 0：那么属于正好可以构成m叉树
- (n0 - 1)%(m - 1) = u：那么属于由u个多余，我们需要加上m - u - 1个虚段

最后：错题的一些问题：

对于任意序列进行基于比较的排序，至少要进行多少次关键字之间的比较，这个至少很魔性，可以这样理解，既然是对任意序列，那么至少就是取最差的情况下限，每次比较两个关键字后，只会出现两种可能的转移，假设整个排序过程至少需要做t次比较，那么显然会出现2^t种情况，那么现在有n个记录，那么会出现n!种排列，所以必须有2^t >= n!，所以t >= log2(n!)，又因为次数是整数，所以需要向上取整
折半插入排序与直接插入排序，两者排序的总趟数取决于元素个数n，至于两者元素的移动次数都是跟初始的序列有关（这个可以看做1的小延伸）
简单选择排序、冒泡排序、堆排序、快速排序每趟排序都可以决定一个元素的最终位置

Comments

😅 Commenting is disabled on this post.

You can use extended GitHub flavored markdown in your comment. Commenting FAQs & Guidelines