---

其他排序算法

一學就廢的歸并排序

---

冒泡排序

排列順序從前到后或者從后往前都可，本文選擇從后到前的順序，升序排列：比較相鄰兩個元素，大的放后面，小的放前面，（降序排列反之）第一個for決定排列數組下標為i的元素，第二個for執行i遍比較過程。
點擊這里可以看到動畫版的冒泡排序【一個很有趣的網站】

---

算法實現

void sort(int* a,int len){//冒泡排序，a為數組首地址，len為數組長度int temp;for(size_t i = len; 0 < i; i--){//確定數組下標為i的元素for(size_t j = 0; j < i; j++){//執行i遍比較過程if(a[j+1] < a[j]){temp = a[j+1];a[j+1] = a[j];a[j] = temp;}}}
}

---

代碼實例

#include <iostream>
using namespace std;void sort(int* a,int len){int temp;for(size_t i = len; 0 < i; i--){//冒泡排序for(size_t j = 0; j < i; j++){if(a[j+1] < a[j]){temp = a[j+1];a[j+1] = a[j];a[j] = temp;}}}
}int main(int argc, char const *argv[]) {int n;while (cin>>n,n) {int a[n];for(int i=0;i < n; i++){cin >> a[i];}int len = sizeof(a)/sizeof(a[0]);sort(a,len);for (int i = 0; i < n; i++) {cout << a[i] << " ";}cout << endl;}}

---

插入排序

排列順序從前到后或者從后往前都可，本文選擇從前到后的順序，每次要確定的數組元素的值要先存入一個臨時變量中（例如下面的temp），再將它之前的元素與它比較，比它大的都往后移動一位（降序排列操作反之），例如：a[7]={1，3，5，2，4，8，7}中，假設此時已經過3輪排序，該執行第4輪排序時，將2賦值給temp，之后將3，5向后移，然后將temp的值賦給a[2]，這樣就相當于做了一個將2插入1，3之間的操作。每個元素都做這樣一個操作之后，整個數組便完成排序了。

ps：上文的網站也可以看插入排序

---

算法實現

void sort(int* a,int len) {//插入排序，升序排列int temp,i,j;for(i = 1; i < len; i++){//決定第i個元素temp = a[i];//先將要插入的值賦給臨時變量防止以數據丟失for(j = i; 0 < j; j--){//執行i遍比較if(temp < a[j-1]){//a[i]之前的元素比temp大的往后移一位a[j] = a[j-1];}else{break;//找到了該插入的位置，退出本層循環，決定下一個元素的位置}}a[j] = temp;//將元素插入到其該存在的位置}
}

---

代碼實例

#include<iostream>
using namespace std;void sort(int* a,int len) {//插入排序，升序排列int temp,i,j;for(i = 1; i < len; i++){//決定第i個元素temp = a[i];for(j = i; 0 < j; j--){//執行i-1遍比較if(temp < a[j-1]){a[j] = a[j-1];}else{break;}}a[j] = temp;}
}int main(int argc, char const *argv[]) {int n;while (cin>>n,n) {int a[n];for(int i=0;i < n; i++){cin >> a[i];}int len = sizeof(a)/sizeof(a[0]);sort(a,len);for (int i = 0; i < n; i++) {cout << a[i] << " ";}cout << endl;}return 0;
}

---

選擇排序

排列順序從前到后或者從后往前都可，本文選擇從前到后的順序，每次要確定的數組元素的值要先存入一個臨時變量中（例如下面的min），再將它之后的元素與它比較，如果某位置的元素比該位置元素值小（降序排列操作反之），則交換兩個位置的元素，并更新min的值，例如：a[7]={1，4，5，3，2，8，7}中，假設此時已經過1輪排序，該執行第2輪排序時，將4賦值給min，之后判定到a[3]時，發現min的值大于a[3]（4>3），交換a[1]和a[3]的元素，也就是數組變成了a[7]={1，3，5，4，2，8，7}，并更新min的值(min = 3)，接下來繼續往后比較時發現min的值大于a[4] (3>2)，則重復之前的操作，交換a[1]與a[4]的內容，也就是數組變成了a[7]={1，2，5，4，3，8，7}，并更新min的值（min = 2），之后再無數組元素值小于min，遍歷完成，一輪排序結束。每個位置（除了最后一個位置，其他位置排好了之后，最后一個位置的元素自然而然就排好了）都做這樣一個操作之后，整個數組便完成排序了。
ps：上文的網站也可以看選擇排序

---

算法實現

void sort(int* a,int len) {//選擇排序，升序排列int min,i,j;for(i = 0; i < len-1; i++){//確定數組下標為i的元素min = a[i];//min作為臨時變量存儲當前最小的值for(j = i+1; j < len; j++){//執行n-i-1遍比較if(min > a[j]){//如果j位置的元素比i位置元素值小，則交換兩個位置的元素，并更新min的值a[i] = a[j];a[j] = min;min = a[i];}}}
}

---

代碼實例

#include<iostream>
using namespace std;void sort(int* a,int len) {//選擇排序，升序排列int min,i,j;for(i = 0; i < len-1; i++){//確定數組下標為i的元素min = a[i];//min作為臨時變量存儲當前最小的值for(j = i+1; j < len; j++){//執行n-i-1遍比較if(min > a[j]){a[i] = a[j];a[j] = min;min = a[i];}}}
}int main(int argc, char const *argv[]) {int n;while (cin>>n,n) {int a[n];for(int i=0;i < n; i++){cin >> a[i];}int len = sizeof(a)/sizeof(a[0]);sort(a,len);for (int i = 0; i < n; i++) {cout << a[i] << " ";}cout << endl;}return 0;
}