【初赛】各种排序算法总结

一、算法评价

其中，冒泡和插入在数据有序时复杂度为只需要O(n)，快速排序在数据有序时退化到O(n^2).

二、代码实现

1、冒泡排序

• 循环n次，每次相邻的数据两两比较,小数放前面,大数放后面
• 这样每一次操作过后最小的数就被排在了最前面

void BubbleSort(int a[], int n){
    for(int i = 1; i < n; i++){ //循环有序数组,每次循环后保证到i位置的值是有序的。
        for(int j = n; j > i; j--) //循环无序数组两两比较
            if(a[j] < a[j-1])swap(a[j],a[j-1]); //如果是逆序对就交换(保证每次把最小的值往前交换)
        //Print(a,n);
    }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
 

2、选择排序

• 在未排序序列中找到最小的元素,记录位置
• 将它放到已排序序列的末尾(和第一个无序元素交换即可)

void SelecSort(int a[], int n){
    for(int i = 1; i <= n; i++){ //对于每一个位置的值(实质是未排序序列的第一个元素)
        int index = i;  //index：记录未排序序列中最小元素的位置
        for(int j = i+1; j <= n; j++) //遍历剩余未排序序列
            if(a[j] < a[index])index = j; //保证index是最小元素的位置
        swap(a[i],a[index]);//将最小的值放到未排序序列的第一个,完成排序
        //for(int i = 1; i <= n; i++)cout<<a[i]<<" ";  cout<<"\n";
    }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
 

3、插入排序

• 数据分为两部分,一开始有序部分包含1个元素
• 依次将无序部分的元素插入到有序部分当中

void InsertSort(int a[], int n){  //直接插入排序
    for(int i = 2; i <= n; i++){ //遍历无序部分,每次取出第一个元素
        int j = i-1, k = a[i];  //j为当前下标, k为无序部分第一个元素
        while(j>=1 && k<a[j]){ //找到k元素在有序部分的位置
            a[j+1] = a[j];    //循环的时候直接右移有序数组,为k腾出位置
            j--;             //不是k正确的位置,继续往前循环
        }
        a[j+1] = k;  //出来的时候j多减了1,要加回去
        //for(int i = 1; i <= n; i++)cout<<a[i]<<" ";  cout<<"\n";
    }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
 

4、快速排序

• 每次选择一个基准数,把比之小的都放到其左边,大的都放到其右边
• 排放时候的细节

void QuickSort(int a[], int n, int l, int r){
    if(l > r)return ; //递归出口,越界返回
    int k = a[l];//k就是基准数(k的选取与内循环的找数顺序有关)
    int i = l, j = r;//区间
    while(i < j){ //i==j时,两数相遇,
        //顺序有影响,先从右往左找,找到第一个比基准数小的位置
        while(i<j && a[j]>=k)j--;//切记‘>=’(可以忽略掉与k相等的值,不然i永远不会大于j,则死循环)
        //然后从左往右找到第一个比基准数大的位置
        while(i<j && a[i]<=k)i++;
        //如果他们没有相遇,就交换这两个数的位置,并继续寻找
        if(i < j)swap(a[i],a[j]);
    }
    //将基准数归位
    a[l] = a[i];  //相遇的位置
    a[i] = k;    //
    QuickSort(a,n,l,i-1);//递归后不用考虑基准数
    QuickSort(a,n,i+1,r);
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
 

5、归并排序

• 先使每个子序列有序，再使子序列段间有序。
• 递归到底层子序列自然有序，段间有序要求每次去合并

void MergeSort(int a[], int n, int l, int r){
    if(l == r)return ;
    int mid = l+r>>1;
    MergeSort(a,n,1,mid);
    MergeSort(a,n,mid+1,r);
    int i = 1, j = mid+1;
    int c[r-l+1], k = 1;
    while(i <= mid && j <= r){
        if(a[i]<a[j])c[k++] = a[i++];
        else c[k++] = a[j++];
    }
    while(i <= mid)c[k++] = a[i++];
    while(j <= r)c[k++] = a[j++];
    for(int i = l; i <= r; i++)
        a[i] = c[i];
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
 

6、堆排序

  

 

  
1
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/83010852