十大經(jīng)典排序算法(動(dòng)態(tài)演示代碼)

copy_left 2020-05-30

展開全文

作者丨自成一派123

來源丨C語言與CPP編程

以前也零零碎碎發(fā)過一些排序算法，但排版都不太好，又重新整理一次，排序算法是數(shù)據(jù)結(jié)構(gòu)的重要部分，系統(tǒng)地學(xué)習(xí)很有必要。

時(shí)間、空間復(fù)雜度比較

1 冒泡排序

算法思想：

1.比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。

2.對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后，最后的元素會(huì)是最大的數(shù)。

3.針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。

4.持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

代碼：

{
  for(int i =0 ; i< n-1; ++i)
  {
    for(int j = 0; j < n-i-1; ++j)
    {
      if(a[j] > a[j+1])
      {
        int tmp = a[j] ;  //交換
        a[j] = a[j+1] ;
        a[j+1] = tmp;
      }
    }
  }
}

2 選擇排序

算法思想：

1.在未排序序列中找到最小（大）元素，存放到排序序列的起始位置

2.從剩余未排序元素中繼續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾

3.以此類推，直到所有元素均排序完畢

代碼：

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     // 尋找最小的數(shù)
                minIndex = j;                 // 將最小數(shù)的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

3 插入排序

算法思想：

1.從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序

2.取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描

3.如果該元素（已排序）大于新元素，將該元素移到下一位置

4.重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置

5.將新元素插入到該位置后

6.重復(fù)步驟2~5

代碼：

void print(int a[], int n ,int i){
  cout<<i <<':';
  for(int j= 0; j<8; j++){
    cout<<a[j] <<' ';
  }
  cout<<endl;
}
void InsertSort(int a[], int n)
{
  for(int i= 1; i<n; i++){
    if(a[i] < a[i-1]){   //若第i個(gè)元素大于i-1元素，直接插入。小于的話，移動(dòng)有序表后插入
      int j= i-1;
      int x = a[i];     //復(fù)制為哨兵，即存儲(chǔ)待排序元素
      a[i] = a[i-1];           //先后移一個(gè)元素
      while(x < a[j]){   //查找在有序表的插入位置
        a[j+1] = a[j];
        j--;     //元素后移
      }
      a[j+1] = x;     //插入到正確位置
    }
    print(a,n,i);      //打印每趟排序的結(jié)果
  }

}

int main(){
  int a[15] = {2，3,4,5,15，19，16，27，36，38，44，46，47，48，50};
  InsertSort(a,15);
  print(a,15,15);
}

4 快速排序

算法思想：

1.選取第一個(gè)數(shù)為基準(zhǔn)2.將比基準(zhǔn)小的數(shù)交換到前面，比基準(zhǔn)大的數(shù)交換到后面3.對(duì)左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個(gè)數(shù)

代碼：

void QuickSort(vector<int>& v, int low, int high) {
	if (low >= high)		// 結(jié)束標(biāo)志
		return;
	int first = low;		// 低位下標(biāo)
	int last = high;		// 高位下標(biāo)
	int key = v[first];		// 設(shè)第一個(gè)為基準(zhǔn)

	while (first < last)
	{
		// 將比第一個(gè)小的移到前面
		while (first < last && v[last] >= key)
			last--;
		if (first < last)
			v[first++] = v[last];

		// 將比第一個(gè)大的移到后面
		while (first < last && v[first] <= key)
			first++;
		if (first < last)
			v[last--] = v[first];
	}
	//
	v[first] = key;
	// 前半遞歸
	QuickSort(v, low, first - 1);
	// 后半遞歸
	QuickSort(v, first + 1, high);
}

5 堆排序

堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。

算法思想：

1.將初始待排序關(guān)鍵字序列(R1,R2….Rn)構(gòu)建成大頂堆，此堆為初始的無序區(qū)；

2.將堆頂元素R[1]與最后一個(gè)元素R[n]交換，此時(shí)得到新的無序區(qū)(R1,R2,……Rn-1)和新的有序區(qū)(Rn),且滿足R[1,2…n-1]<=R[n]；

3.由于交換后新的堆頂R[1]可能違反堆的性質(zhì)，因此需要對(duì)當(dāng)前無序區(qū)(R1,R2,……Rn-1)調(diào)整為新堆，然后再次將R[1]與無序區(qū)最后一個(gè)元素交換，得到新的無序區(qū)(R1,R2….Rn-2)和新的有序區(qū)(Rn-1,Rn)。不斷重復(fù)此過程直到有序區(qū)的元素個(gè)數(shù)為n-1，則整個(gè)排序過程完成。

代碼：

#include <iostream>
#include <algorithm>
using namespace std;

// 堆排序：（最大堆，有序區(qū)）。從堆頂把根卸出來放在有序區(qū)之前，再恢復(fù)堆。

void max_heapify(int arr[], int start, int end) {
	//建立父節(jié)點(diǎn)指標(biāo)和子節(jié)點(diǎn)指標(biāo)
	int dad = start;
	int son = dad * 2 + 1;
	while (son <= end) { //若子節(jié)點(diǎn)在范圍內(nèi)才做比較
		if (son + 1 <= end && arr[son] < arr[son + 1]) //先比較兩個(gè)子節(jié)點(diǎn)指標(biāo)，選擇最大的
			son++;
		if (arr[dad] > arr[son]) //如果父節(jié)點(diǎn)大于子節(jié)點(diǎn)代表調(diào)整完成，直接跳出函數(shù)
			return;
		else { //否則交換父子內(nèi)容再繼續(xù)子節(jié)點(diǎn)與孫節(jié)點(diǎn)比較
			swap(arr[dad], arr[son]);
			dad = son;
			son = dad * 2 + 1;
		}
	}
}

void heap_sort(int arr[], int len) {
	//初始化，i從最后一個(gè)父節(jié)點(diǎn)開始調(diào)整
	for (int i = len / 2 - 1; i >= 0; i--)
		max_heapify(arr, i, len - 1);
	//先將第一個(gè)元素和已經(jīng)排好的元素前一位做交換，再從新調(diào)整(剛調(diào)整的元素之前的元素)，直到排序完成
	for (int i = len - 1; i > 0; i--) {
		swap(arr[0], arr[i]);
		max_heapify(arr, 0, i - 1);
	}
}

int main() {
	int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
	int len = (int) sizeof(arr) / sizeof(*arr);
	heap_sort(arr, len);
	for (int i = 0; i < len; i++)
		cout << arr[i] << ' ';
	cout << endl;
	return 0;
}

6 歸并排序

歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為2-路歸并。

算法思想：

1.把長度為n的輸入序列分成兩個(gè)長度為n/2的子序列；

2.對(duì)這兩個(gè)子序列分別采用歸并排序；

3.將兩個(gè)排序好的子序列合并成一個(gè)最終的排序序列。

代碼：

void print(int a[], int n){
  for(int j= 0; j<n; j++){
    cout<<a[j] <<'  ';
  }
  cout<<endl;
}

//將r[i…m]和r[m +1 …n]歸并到輔助數(shù)組rf[i…n]
void Merge(ElemType *r,ElemType *rf, int i, int m, int n)
{
  int j,k;
  for(j=m+1,k=i; i<=m && j <=n ; ++k){
    if(r[j] < r[i]) rf[k] = r[j++];
    else rf[k] = r[i++];
  }
  while(i <= m)  rf[k++] = r[i++];
  while(j <= n)  rf[k++] = r[j++];
  print(rf,n+1);
}

void MergeSort(ElemType *r, ElemType *rf, int lenght)
{
  int len = 1;
  ElemType *q = r ;
  ElemType *tmp ;
  while(len < lenght) {
    int s = len;
    len = 2 * s ;
    int i = 0;
    while(i+ len <lenght){
      Merge(q, rf,  i, i+ s-1, i+ len-1 ); //對(duì)等長的兩個(gè)子表合并
      i = i+ len;
    }
    if(i + s < lenght){
      Merge(q, rf,  i, i+ s -1, lenght -1); //對(duì)不等長的兩個(gè)子表合并
    }
    tmp = q; q = rf; rf = tmp; //交換q,rf，以保證下一趟歸并時(shí)，仍從q 歸并到rf
  }
}


int main(){
  int a[10] = {2，3,4，5,15,19,26,27,36,38,44,46,47,48,50};
  int b[10];
  MergeSort(a, b, 15);
  print(b,15);
  cout<<'結(jié)果：';
  print(a,10);
}

7 希爾排序

希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進(jìn)版本。但希爾排序是非穩(wěn)定排序算法。先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序.

算法思想：

1.選擇一個(gè)增量序列t1，t2，…，tk，其中ti>tj，tk=1；

2.按增量序列個(gè)數(shù)k，對(duì)序列進(jìn)行k 趟排序；

3.每趟排序，根據(jù)對(duì)應(yīng)的增量ti，將待排序列分割成若干長度為m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序。僅增量因子為1 時(shí)，整個(gè)序列作為一個(gè)表來處理，表長度即為整個(gè)序列的長度。

代碼：

void shell_sort(T array[], int length) {
    int h = 1;
    while (h < length / 3) {
        h = 3 * h + 1;
    }
    while (h >= 1) {
        for (int i = h; i < length; i++) {
            for (int j = i; j >= h && array[j] < array[j - h]; j -= h) {
                std::swap(array[j], array[j - h]);
            }
        }
        h = h / 3;
    }
}

8 計(jì)數(shù)排序

計(jì)數(shù)排序統(tǒng)計(jì)小于等于該元素值的元素的個(gè)數(shù)i，于是該元素就放在目標(biāo)數(shù)組的索引i位（i≥0）。

計(jì)數(shù)排序基于一個(gè)假設(shè)，待排序數(shù)列的所有數(shù)均為整數(shù)，且出現(xiàn)在（0，k）的區(qū)間之內(nèi)。

如果 k（待排數(shù)組的最大值）過大則會(huì)引起較大的空間復(fù)雜度，一般是用來排序 0 到 100 之間的數(shù)字的最好的算法，但是它不適合按字母順序排序人名。

計(jì)數(shù)排序不是比較排序，排序的速度快于任何比較排序算法。

算法思想：

找出待排序的數(shù)組中最大和最小的元素；

統(tǒng)計(jì)數(shù)組中每個(gè)值為 i 的元素出現(xiàn)的次數(shù)，存入數(shù)組 C 的第 i 項(xiàng)；

對(duì)所有的計(jì)數(shù)累加（從 C 中的第一個(gè)元素開始，每一項(xiàng)和前一項(xiàng)相加）；

向填充目標(biāo)數(shù)組：將每個(gè)元素 i 放在新數(shù)組的第 C[i] 項(xiàng)，每放一個(gè)元素就將 C[i] 減去 1；

代碼：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 計(jì)數(shù)排序
void CountSort(vector<int>& vecRaw, vector<int>& vecObj)
{
	// 確保待排序容器非空
	if (vecRaw.size() == 0)
		return;

	// 使用 vecRaw 的最大值 + 1 作為計(jì)數(shù)容器 countVec 的大小
	int vecCountLength = (*max_element(begin(vecRaw), end(vecRaw))) + 1;
	vector<int> vecCount(vecCountLength, 0);

	// 統(tǒng)計(jì)每個(gè)鍵值出現(xiàn)的次數(shù)
	for (int i = 0; i < vecRaw.size(); i++)
		vecCount[vecRaw[i]]++;
	
	// 后面的鍵值出現(xiàn)的位置為前面所有鍵值出現(xiàn)的次數(shù)之和
	for (int i = 1; i < vecCountLength; i++)
		vecCount[i] += vecCount[i - 1];

	// 將鍵值放到目標(biāo)位置
	for (int i = vecRaw.size(); i > 0; i--)	// 此處逆序是為了保持相同鍵值的穩(wěn)定性
		vecObj[--vecCount[vecRaw[i - 1]]] = vecRaw[i - 1];
}

int main()
{
	vector<int> vecRaw = { 0,5,7,9,6,3,4,5,2,8,6,9,2,1 };
	vector<int> vecObj(vecRaw.size(), 0);

	CountSort(vecRaw, vecObj);

	for (int i = 0; i < vecObj.size(); ++i)
		cout << vecObj[i] << '  ';
	cout << endl;

	return 0;
}

9 桶排序

將值為i的元素放入i號(hào)桶，最后依次把桶里的元素倒出來。

算法思想：

1.設(shè)置一個(gè)定量的數(shù)組當(dāng)作空桶子。2.尋訪序列，并且把項(xiàng)目一個(gè)一個(gè)放到對(duì)應(yīng)的桶子去。3.對(duì)每個(gè)不是空的桶子進(jìn)行排序。4.從不是空的桶子里把項(xiàng)目再放回原來的序列中。

代碼：

function bucketSort(arr, bucketSize) {
    if (arr.length === 0) {
      return arr;
    }
 
    var i;
    var minValue = arr[0];
    var maxValue = arr[0];
    for (i = 1; i < arr.length; i++) {
      if (arr[i] < minValue) {
          minValue = arr[i];                // 輸入數(shù)據(jù)的最小值
      } else if (arr[i] > maxValue) {
          maxValue = arr[i];                // 輸入數(shù)據(jù)的最大值
      }
    }
 
    // 桶的初始化
    var DEFAULT_BUCKET_SIZE = 5;            // 設(shè)置桶的默認(rèn)數(shù)量為5
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
    var buckets = new Array(bucketCount);
    for (i = 0; i < buckets.length; i++) {
        buckets[i] = [];
    }
 
    // 利用映射函數(shù)將數(shù)據(jù)分配到各個(gè)桶中
    for (i = 0; i < arr.length; i++) {
        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
    }
 
    arr.length = 0;
    for (i = 0; i < buckets.length; i++) {
        insertionSort(buckets[i]);                      // 對(duì)每個(gè)桶進(jìn)行排序，這里使用了插入排序
        for (var j = 0; j < buckets[i].length; j++) {
            arr.push(buckets[i][j]);
        }
    }
 
    return arr;
}

10 基數(shù)排序

一種多關(guān)鍵字的排序算法，可用桶排序?qū)崿F(xiàn)。

算法思想：

1.取得數(shù)組中的最大數(shù)，并取得位數(shù)；2.arr為原始數(shù)組，從最低位開始取每個(gè)位組成radix數(shù)組；3.對(duì)radix進(jìn)行計(jì)數(shù)排序（利用計(jì)數(shù)排序適用于小范圍數(shù)的特點(diǎn)）

代碼：

int maxbit(int data[], int n) //輔助函數(shù)，求數(shù)據(jù)的最大位數(shù)
{
    int maxData = data[0];		///< 最大數(shù)
    /// 先求出最大數(shù)，再求其位數(shù)，這樣有原先依次每個(gè)數(shù)判斷其位數(shù)，稍微優(yōu)化點(diǎn)。
    for (int i = 1; i < n; ++i)
    {
        if (maxData < data[i])
            maxData = data[i];
    }
    int d = 1;
    int p = 10;
    while (maxData >= p)
    {
        //p *= 10; // Maybe overflow
        maxData /= 10;
        ++d;
    }
    return d;
/*    int d = 1; //保存最大的位數(shù)
    int p = 10;
    for(int i = 0; i < n; ++i)
    {
        while(data[i] >= p)
        {
            p *= 10;
            ++d;
        }
    }
    return d;*/
}
void radixsort(int data[], int n) //基數(shù)排序
{
    int d = maxbit(data, n);
    int *tmp = new int[n];
    int *count = new int[10]; //計(jì)數(shù)器
    int i, j, k;
    int radix = 1;
    for(i = 1; i <= d; i++) //進(jìn)行d次排序
    {
        for(j = 0; j < 10; j++)
            count[j] = 0; //每次分配前清空計(jì)數(shù)器
        for(j = 0; j < n; j++)
        {
            k = (data[j] / radix) % 10; //統(tǒng)計(jì)每個(gè)桶中的記錄數(shù)
            count[k]++;
        }
        for(j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j]; //將tmp中的位置依次分配給每個(gè)桶
        for(j = n - 1; j >= 0; j--) //將所有桶中記錄依次收集到tmp中
        {
            k = (data[j] / radix) % 10;
            tmp[count[k] - 1] = data[j];
            count[k]--;
        }
        for(j = 0; j < n; j++) //將臨時(shí)數(shù)組的內(nèi)容復(fù)制到data中
            data[j] = tmp[j];
        radix = radix * 10;
    }
    delete []tmp;
    delete []count;
}
? 2020 GitHub, Inc.

參考資料

1.https://www.cnblogs.com/onepixel/p/7674659.html(部分動(dòng)圖來源)

2.電子工程專輯

本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊一鍵舉報(bào)。

轉(zhuǎn)藏 分享

QQ空間 QQ好友新浪微博微信

獻(xiàn)花（0） +1

來自： copy_left > 《待分類》

舉報(bào)/認(rèn)領(lǐng)