常用的排序算法总结
常用的排序算法
一、冒泡排序
冒泡排序（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²)，平均的时间复杂度是O(n logn)。
假设被排序的数列中有n个数。遍历一次的时间复杂度是O(n)，需要遍历多少次呢？至少log(n+1)次，最多n次。
1.为什么最少是log(n+1)次？快速排序是采用的分治法进行遍历的，我们将它看作一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的定义，它的深度至少是log(n+1)。因此，快速排序的遍历次数最少是log(n+1)次。
2.为什么最多是n次？这个应该非常简单，还是将快速排序看作一棵二叉树，它的深度最大是N。因此，快读排序的遍历次数最多是n次。
六、归并排序
#include<cstdio>
using namespace std;
int n,x[1000],z[1000];
void merge_sort(int L,int R)
{
if (L==R) return;
int mid=(L+R)/2;
merge_sort(L,mid);merge_sort(mid+1,R);
int i=L,j=mid+1,k=L;
while (i<=mid && j<=R)
if (x[i]<x[j])
z[k++]=x[i++];
else
z[k++]=x[j++];
while (i<=mid) z[k++]=x[i++];
while (j<=R) z[k++]=x[j++];
for (int i=L;i<=R;i++) x[i]=z[i];
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&x[i]);
merge_sort(1,n);
for (int i=1;i<=n;i++)
printf("%d ",x[i]);
printf("\n");
return 0;
}
时间复杂度：O(n logn)。
空间复杂度：O(n)，归并排序需要一个与原数组相同长度的数组做辅助来排序。
稳定性：在数据量大且数据递增或递减连续性好的情况下，效率比较高，且是O(n logn)复杂度下唯一一个稳定的排序。
七、堆排序
#include<cstdio>
using namespace std;
int n,x[100];
void check(int v,int nmax){
int k=2*v,t;
if (k>nmax) return;
if (k+1>nmax) {
if (x[v]>x[k])
t=x[k],x[k]=x[v],x[v]=t;
return;
}
int j=k;if (x[k]>x[k+1]) j=k+1;
if (x[v]>x[j]) {
t=x[j],x[j]=x[v],x[v]=t;
check(j,nmax);
}
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&x[i]);
for (int i=n/2;i>=1;i--)
check(i,n);
int m=n;
for (int i=1;i<=m;i++) {
printf("%d ",x[1]);
x[1]=x[n];n--;check(1,n);
}
printf("\n");
return 0;
}
八、sort排序
#include <bits/stdc++.h>
using namespace std;
int a[114514],n;
int main() {
scanf("%d",&n);
for (int i = 0; i < n; i++)
scanf("%d",&a[i]);
sort(a, a + n);
for (int i = 0; i < n; i++)
printf("%d ",a[i]);
printf("\n");
return 0;
}
热门相关：斗神战帝 特工重生：快穿全能女神 朕是红颜祸水 无限杀路 梦回大明春