常用的排序演算法

一、冒泡排序

冒泡排序（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; 
}