常用的排序演算法
一、冒泡排序
冒泡排序（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(n2)
二、選擇排序
選擇排序法是一種不穩定的排序演算法，它的作業原理是每一次從待排序的資料元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然后，再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾，
以此類推，直到全部待排序的資料元素排完，
#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(n2)，選擇排序是一個不穩定的排序演算法，
三、插入排序
插入排序是指在待排序的元素中，假設前面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(n2)
四、桶排序
#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(n2)，平均的時間復雜度是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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/553745.html
標籤：其他
下一篇：返回列表