下個月又將舉行信息奧賽了，一起來複習十大經典排序算法。
冒泡排序動圖演示
代碼：void bubbleSort(int a[], int n)
{
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 選擇排序在未排序序列中找到最小（大）元素，存放到排序序列的起始位置從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾代碼：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]) { // 尋找最小的數
minIndex = j; // 將最小數的索引保存
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
3 插入排序取出下一個元素，在已經排序的元素序列中從後向前掃描如果該元素（已排序）大於新元素，將該元素移到下一位置重複步驟3，直到找到已排序的元素小於或者等於新元素的位置代碼：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個元素大於i-1元素，直接插入。小於的話，移動有序表後插入
int j= i-1;
int x = a[i]; //複製為哨兵，即存儲待排序元素
a[i] = a[i-1]; //先後移一個元素
while(x < a[j]){ //查找在有序表的插入位置
a[j+1] = a[j];
j--; //元素後移
}
a[j+1] = x; //插入到正確位置
}
print(a,n,i); //列印每趟排序的結果
}
}
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 快速排序代碼：void QuickSort(vector<int>& v, int low, int high) {
if (low >= high) // 結束標誌
return;
int first = low; // 低位下標
int last = high; // 高位下標
int key = v[first]; // 設第一個為基準
while (first < last)
{
// 將比第一個小的移到前面
while (first < last && v[last] >= key)
last--;
if (first < last)
v[first++] = v[last];
// 將比第一個大的移到後面
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）是指利用堆這種數據結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子節點的鍵值或索引總是小於（或者大於）它的父節點。將初始待排序關鍵字序列(R1,R2….Rn)構建成大頂堆，此堆為初始的無序區；將堆頂元素R[1]與最後一個元素R[n]交換，此時得到新的無序區(R1,R2,……Rn-1)和新的有序區(Rn),且滿足R[1,2…n-1]<=R[n]；由於交換後新的堆頂R[1]可能違反堆的性質，因此需要對當前無序區(R1,R2,……Rn-1)調整為新堆，然後再次將R[1]與無序區最後一個元素交換，得到新的無序區(R1,R2….Rn-2)和新的有序區(Rn-1,Rn)。不斷重複此過程直到有序區的元素個數為n-1，則整個排序過程完成。代碼：#include <iostream>
#include <algorithm>
using namespace std;
// 堆排序：（最大堆，有序區）。從堆頂把根卸出來放在有序區之前，再恢復堆。
void max_heapify(int arr[], int start, int end) {
//建立父節點指標和子節點指標
int dad = start;
int son = dad * 2 + 1;
while (son <= end) { //若子節點在範圍內才做比較
if (son + 1 <= end && arr[son] < arr[son + 1]) //先比較兩個子節點指標，選擇最大的
son++;
if (arr[dad] > arr[son]) //如果父節點大於子節點代表調整完成，直接跳出函數
return;
else { //否則交換父子內容再繼續子節點與孫節點比較
swap(arr[dad], arr[son]);
dad = son;
son = dad * 2 + 1;
}
}
}
void heap_sort(int arr[], int len) {
//初始化，i從最後一個父節點開始調整
for (int i = len / 2 - 1; i >= 0; i--)
max_heapify(arr, i, len - 1);
//先將第一個元素和已經排好的元素前一位做交換，再從新調整(剛調整的元素之前的元素)，直到排序完成
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）的一個非常典型的應用。將已有序的子序列合併，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合併成一個有序表，稱為2-路歸併。算法思想：1.把長度為n的輸入序列分成兩個長度為n/2的子序列；2. 對這兩個子序列分別採用歸併排序；3. 將兩個排序好的子序列合併成一個最終的排序序列。代碼：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]歸併到輔助數組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 ); //對等長的兩個子表合併
i = i+ len;
}
if(i + s < lenght){
Merge(q, rf, i, i+ s -1, lenght -1); //對不等長的兩個子表合併
}
tmp = q; q = rf; rf = tmp; //交換q,rf，以保證下一趟歸併時，仍從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<<"結果：";
print(a,10);
}
7 希爾排序希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。但希爾排序是非穩定排序算法。先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序.選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1；每趟排序，根據對應的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。代碼：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 計數排序計數排序統計小於等於該元素值的元素的個數i，於是該元素就放在目標數組的索引i位（i≥0）。計數排序基於一個假設，待排序數列的所有數均為整數，且出現在（0，k）的區間之內。如果 k（待排數組的最大值） 過大則會引起較大的空間複雜度，一般是用來排序 0 到 100 之間的數字的最好的算法，但是它不適合按字母順序排序人名。計數排序不是比較排序，排序的速度快於任何比較排序算法。統計數組中每個值為 i 的元素出現的次數，存入數組 C 的第 i 項；對所有的計數累加（從 C 中的第一個元素開始，每一項和前一項相加）；向填充目標數組：將每個元素 i 放在新數組的第 C[i] 項，每放一個元素就將 C[i] 減去 1；代碼：#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 計數排序
void CountSort(vector<int>& vecRaw, vector<int>& vecObj)
{
// 確保待排序容器非空
if (vecRaw.size() == 0)
return;
// 使用 vecRaw 的最大值 + 1 作為計數容器 countVec 的大小
int vecCountLength = (*max_element(begin(vecRaw), end(vecRaw))) + 1;
vector<int> vecCount(vecCountLength, 0);
// 統計每個鍵值出現的次數
for (int i = 0; i < vecRaw.size(); i++)
vecCount[vecRaw[i]]++;
// 後面的鍵值出現的位置為前面所有鍵值出現的次數之和
for (int i = 1; i < vecCountLength; i++)
vecCount[i] += vecCount[i - 1];
// 將鍵值放到目標位置
for (int i = vecRaw.size(); i > 0; i--) // 此處逆序是為了保持相同鍵值的穩定性
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號桶，最後依次把桶裡的元素倒出來。代碼：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]; // 輸入數據的最小值
} else if (arr[i] > maxValue) {
maxValue = arr[i]; // 輸入數據的最大值
}
}
// 桶的初始化
var DEFAULT_BUCKET_SIZE = 5; // 設置桶的默認數量為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] = [];
}
// 利用映射函數將數據分配到各個桶中
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]); // 對每個桶進行排序，這裡使用了插入排序
for (var j = 0; j < buckets[i].length; j++) {
arr.push(buckets[i][j]);
}
}
return arr;
}
10 基數排序arr為原始數組，從最低位開始取每個位組成radix數組；對radix進行計數排序（利用計數排序適用於小範圍數的特點）代碼：int maxbit(int data[], int n) //輔助函數，求數據的最大位數
{
int maxData = data[0]; ///< 最大數
/// 先求出最大數，再求其位數，這樣有原先依次每個數判斷其位數，稍微優化點。
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; //保存最大的位數
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) //基數排序
{
int d = maxbit(data, n);
int *tmp = new int[n];
int *count = new int[10]; //計數器
int i, j, k;
int radix = 1;
for(i = 1; i <= d; i++) //進行d次排序
{
for(j = 0; j < 10; j++)
count[j] = 0; //每次分配前清空計數器
for(j = 0; j < n; j++)
{
k = (data[j] / radix) % 10; //統計每個桶中的記錄數
count[k]++;
}
for(j = 1; j < 10; j++)
count[j] = count[j - 1] + count[j]; //將tmp中的位置依次分配給每個桶
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++) //將臨時數組的內容複製到data中
data[j] = tmp[j];
radix = radix * 10;
}
delete []tmp;
delete []count;
}
© 2020 GitHub, Inc.本文轉自點擊文末「閱讀原文」，來源https://space.bilibili.com/487923491
待續更多精彩內容.（學習信息技術，就從關注本公眾號開始。）
附錄：
2018年本公眾號信息技術目錄
2019年本公眾號信息技術目錄
以下是今年本公眾號發表的目錄
原創 送給班主任的五個實用小程序
原創 用微信小程序輕鬆去水印原創 用網頁和小程序輕鬆生成二維碼
原創 從各國在AI領域影響力到來自微軟、阿里、騰訊、英偉達、百度、美團的AI
Python教程一：軟體安裝Python教程二：編輯第一個Python程序Python教程三：print函數用法總結
Python教程四：海龜畫直線Python教程五：海龜畫正方形Python教程六：海龜畫五角
Python教程七：for循環
Python教程八：range函數Python教程九 計算機思維Python教程十：總複習
原創 手機觀影三劍客
原創 懶人寫文章的四個寶貝：文章生成器利用軟體解決直播不卡的三個簡單辦法原創 精選5個超實用免費工具，不看絕對後悔！
原創 已修改 手機變音軟體哪個好
麥克風沒聲或雜音，這個選項你注意到了嗎
原創 404 也能訪問啦，就這！
原創 為微信頭像戴口罩超簡單，就這！
一個6M的網盤搜索神器，就這！足不出戶學趣味編程的三個網站
PPT內嵌視頻（指發布時只需要ppt一個文件即可）
一款全能的pdf工具，就6M
原創 輕鬆做動態圖表神器，就這
靠譜綠色軟體哪裡找，就這
原創 幾秒去除電腦彈窗廣告，就這！
用一行代碼實現網頁變灰效果，就這！原創 一個簡單、良心的免費電子圖書下載網站，就這
原創 送三個下載軟體的好地方，就這
原創 有聲小說全免費，就這！
原創 手機快沒電時先關機會省電嗎？送省電壁原創 推薦一個配音神器，就這
原創 手機清理垃圾神器，就這！
微信早報生成器，全自動，就這！
原創 一款文本轉手寫的轉化工具，還送原始碼！
原創 一行代碼開啟電腦的上帝模式，就這！
原創 電腦插入U盤提示格式化怎麼辦？原創 一分鐘破解Excle密碼保護，就這！
三個酷酷的Windows命令行指令，就這！5秒鐘讓手機重生，就這！
AR Cut & Paste
2013-2018 年期間的信息學競賽課件五大黑科技網站推薦
原創 我壓箱底的資源網站，就這可以啃任何生肉的翻譯軟體，就這
原創 公司內網怎麼不能正常登錄？
原創 直接打開攝像頭就能實時取色，就這
Excel如何列印又細又長的表格
原創 最強搜索，就這！
如何自學計算機科學的指南，這有最好的
分享一款理工生必備神器：Wolfram Alpha
原創 用手機輕鬆30秒把腿變長變細，就這
原創 模糊文字變清晰用PS27秒，小工具3秒
原創 已修改 用PS摳複雜背景的人物15秒，AI
Python 我說幾句，送學習體會
發現個很不錯的設計網站，就這！
《實用的 Python 編程》
可自動為書籍創建 3D 圖像，就這！
原創 身份證照片列印出複印效果，就這
PS銀變金的小技巧，簡單實用
原創 一個超棒的視頻解析網站
原創 快速輕鬆移除視頻背景的小工具，超實用
原創 免費的編程中文書籍索引，就這
原創 用PS秒做雙眼皮
編程學習網站：Studytonight
原創 大量PPT免費模板隨意下，就這
原創 製作可啟動 U 盤的裝機神器：Ventoy
原創 滿分作文生成器
原創 用地圖來探尋全球的電臺，給眼睛放放假
原創 推薦一款高精度免費 OCR 工具：TextShot
原創 用PS輕鬆10秒把照片放進水晶裡
VX學籍拍照助手
原創 推薦一個工具箱
原創 好勵志：盲人程式設計師獨立開發吃雞遊戲
原創 推薦一個小說搜尋引擎