常用的排序算法
一、冒泡排序
冒泡排序（Bubble Sort），是一种较简单的排序算法。
它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
#include<cstdio>
using namespace std;
int n,x[100];
int main()
{
scanf("%d",&n);
for (int i=0;i<n;i++)
scanf("%d",&x[i]);
for (int t,i=0; i<n-1; i++) /* 外循环为排序趟数，n个数进行n-1趟 */
for (int j=0; j<n-1-i; j++) { /* 内循环为每趟比较的次数，第i趟比较n-i次 */
if (x[j] > x[j+1]) { /* 相邻元素比较，若逆序则交换（升序为左大于右，降序反之） */
t = x[j];
x[j] = x[j+1];
x[j+1] = t;
}
}
for (int i=0; i<n; i++)
printf("%d ", x[i]);
printf("\n");
return 0;
}
时间复杂度O(n²)
二、选择排序
选择排序法是一种不稳定的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
以此类推，直到全部待排序的数据元素排完。
#include<cstdio>
using namespace std;
int n,x[100];
int main()
{
scanf("%d",&n);
for (int i=0;i<n;i++)
scanf("%d",&x[i]);
for(int t,i=0;i<n-1;i++)//从首位开始,注意:最后一个数由于已经被动和前面所有数进行了比较,故不需要再主动比较
{
int k=i;
for(int j=i+1;j<n;j++)//依次和后面的数比较找出最小的数
if(x[j]<x[k])
k=j;
if(k != i)//如果最小的数不是首位,则交换
t=x[k],x[k]=x[i],x[i]=t;
}
for (int i=0; i<n; i++)
printf("%d ", x[i]);
printf("\n");
return 0;
}
时间复杂度O(n²)，选择排序是一个不稳定的排序算法。
三、插入排序
插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。
按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序 。
#include<cstdio>
using namespace std;
int n,x[100];
int main()
{
scanf("%d",&n);
for (int i=0;i<n;i++)
scanf("%d",&x[i]);
for (int pos,cur,i=1; i<n; i++)
{
pos = i-1 ; //有序序列的最后一个元素位置
cur = x[i]; //保存待排序元素的值
while (pos >= 0 && x[pos] > cur)
{
x[pos + 1] = x[pos];
pos--;
}
x[pos + 1] = cur; //将待排序元素插入数组中
}
for (int i=0; i<n; i++)
printf("%d ", x[i]);
printf("\n");
return 0;
}
时间复杂度O(n²)
四、桶排序
#include <bits/stdc++.h>
using namespace std;
int a[1010];
int n, x, s ;
int main() {
scanf("%d",&n);
for (int i = 0; i < n; i++) {
scanf("%d",&x);
a[x]++;
if (a[x] == 1) {
s++;
}
}
cout << s << endl;
for (int i = 0; i < n; i++) {
if (a[i] > 0) {
printf("%d ", x[i]);
}
}
printf("\n");
return 0;
}
五、快速排序
快速排序(Quick Sort)使用分治法策略。
它的基本思想是：选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分；其中一部分的所有数据都比另外一部分的所有数据都要小。然后，再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序流程：
(1) 从数列中挑出一个基准值。
(2) 将所有比基准值小的摆放在基准前面，所有比基准值大的摆在基准的后面(相同的数可以到任一边)；在这个分区退出之后，该基准就处于数列的中间位置。
(3) 递归地把"基准值前面的子数列"和"基准值后面的子数列"进行排序。
#include<cstdio>
using namespace std;
int n,x[100];
void qsort(int L,int R) {
int i=L,j=R,mid=x[(i+j)/2],t;
while (i<j) {
while (x[i]<mid) i++;
while (x[j]>mid) j--;
if (i<=j) {
t=x[i],x[i]=x[j],x[j]=t;i++;j--;
}
}
if (i<R) qsort(i,R);
if (L<j) qsort(L,j);
}
int main()
{
scanf("%d",&n);
for (int i=0;i<n;i++)
scanf("%d",&x[i]);
qsort(0,n-1);
for (int i=0; i<n; i++)
printf("%d ", x[i]);
printf("\n");
return 0;
}
快速排序时间复杂度
快速排序的时间复杂度在最坏情况下是O(n