排序算法

· · 个人记录

冒泡排序

冒泡排序动画

原理：相邻数比较

  1. 比较相邻2个数的大小，如果不满足排序顺序，则交换这2个数
  2. 需要比较n-1轮，每轮比较次数递减，为n-i次（i表示第几轮）

代码：

#include<bits/stdc++.h>
using namespace std;
int n, a[101]; 
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>a[i];
    }   
    //冒泡排序， n-1轮，每轮将最大的数沉底 
    for(int i=1; i<=n-1; i++){
        for(int j=1; j<=n-i; j++){
            if(a[j]>a[j+1]){
                swap(a[j], a[j+1]);
            }
        }
    }   
    for(int i=1; i<=n; i++){
        cout<<a[i]<<" ";
    }    
    return 0;
}

选择排序

选择排序动画演示

原理：依次找出最小值，放到前面

  1. 从a[1]到a[n]之间找出最小值放在a[1]的位置
  2. 从a[2]到a[n]之间找出最小值放在a[2]的位置
  3. 从a[3]到a[n]之间找出最小值放在a[3]的位置
  4. 重复执行以上过程，需要做n-1轮，每轮比较次数递减

代码：

for(int i=1; i<=n-1; i++){
    for(int j=i+1; j<=n; j++){
        if(a[j]<a[i]){
            swap(a[j], a[i]);
        }
    }
}

插入排序

插入排序动画演示

原理：通过构建有序序列，对于未排序的数据，在已经排序的序列中从后向前扫描，找到合适的位置后插入

  1. 将a[1]看做已经排好序的有序序列，a[2]到a[n]看做是无序序列，需要依次将他们插入。
  2. 观察a[2]，和a[1]比较，找到合适位置后插入
  3. 观察a[3]，和a[1]——a[2]比较，找到合适位置后插入
  4. 重复执行，直到a[n]插入，如果待插入的元素和有序序列中的某个元素相等，则将待插入的元素插入到相等元素的后面

代码：

//从第2个数开始，依次插入 
for(int i=2; i<=n; i++){
    for(int j=i-1; j>=1; j--){
        if(a[j]>a[j+1]){
            swap(a[j], a[j+1]);
        }
    }
}

STL sort排序

系统函数，对两个迭代器（或指针）指定的部分进行快速排序。可以在第三个参数传入定义大小比较的函数。

把一个int数组（元素存放在下标1 ~ n）从大到小排序，传入比较函数：

int a[MAX_SIZE];
bool cmp(int a, int b)
{
    return a > b; 
}
sort(a + 1, a + n + 1, cmp);

需要特别注意sort函数参数的写法：

  1. 第一个参数是起始位置

  2. 第二个参数是结束位置+1

STL unique去重

去重之前必须先排序，

返回去重（只去掉相邻的相同元素）之后的尾迭代器（或指针），仍然为前闭后开区间，即这个迭代器是去重之后最后一个不重复元素的下一个位置。利用迭代器（或指针）的减法，可计算出去重后的元素个数。

把一个数组去重，元素存放在下标1 ~ n：

//m为去重后不重复数字的个数
sort(a+1, a+n+1);  //必须先排序
int m = unique(a + 1, a + n + 1) – (a + 1);

//输出不重复的数字
for(int i=1; i<=m; i++){
    cout<<a[i]<<" ";
}