冒泡排序

#include<iostream> using namespace std; #define SWAP(a,b) {int tmp;tmp=a;a=b;b=tmp;} int main() {int a[1000];//總數(shù)int total;cout << "請輸入排序的元素個數(shù)：";cin >> total;//輸入數(shù)據(jù)int i;cout << "請輸入要排序的數(shù)字：";for (i = 0; i < total; i++){cin >> a[i];}//冒泡 從小到大int j;for (i = 0; i < total; i++){for (j = 0; j < total - i - 1; j++){if (a[j] > a[j + 1])SWAP(a[j], a[j + 1]);}}//輸出cout << "排序結(jié)果：\n";for (i = 0; i < total; i++){cout << a[i] << " ";}system("pause"); }

選擇排序

#include<iostream> using namespace std; #define SWAP(a,b) {int tmp;tmp=a;a=b;b=tmp;} int main() {int a[1000];//總數(shù)int total;cout << "請輸入排序的元素個數(shù)：";cin >> total;//輸入數(shù)據(jù)int i;cout << "請輸入要排序的數(shù)字：";for (i = 0; i < total; i++){cin >> a[i];}//選擇排序 從小到大int j;int minIndex;int min;for (i = 0; i < total - 1; i++)//i表示最后一個有序元素的位置{//初始化min = a[i];minIndex = i;//找i后面最小元素for (j = i; j < total; j++){if (a[j] < min){min = a[j];minIndex = j;}}//交換SWAP(a[i], a[minIndex]);}//輸出cout << "排序結(jié)果：\n";for (i = 0; i < total; i++){cout << a[i] << " ";}system("pause"); }

插入排序

代碼

#include<iostream> using namespace std; #define SWAP(a,b) {int tmp;tmp=a;a=b;b=tmp;} int main() {int a[1000];//總數(shù)int total;cout << "請輸入排序的元素個數(shù)：";cin >> total;//輸入數(shù)據(jù)int i;cout << "請輸入要排序的數(shù)字：";for (i = 0; i < total; i++){cin >> a[i];}//插入排序 從小到大int j;for (i = 0; i < total; i++){for (j = i; j > 0; j--){if (a[j] < a[j - 1]){SWAP(a[j], a[j - 1]);}}}//輸出cout << "排序結(jié)果：\n";for (i = 0; i < total; i++){cout << a[i] << " ";}system("pause"); }

解釋

普通的插入排序：在數(shù)組空間內(nèi)不斷的交換元素，把想要移動的元素逐步移動到想要插入的位置。這個過程和冒泡排序很像，像是向前冒的冒泡排序。

插入排序步驟：

• 選擇元素
• 尋找合適的插入位置
• 循環(huán)交換中間的元素，將元素交換到想要插入的位置

代碼實現(xiàn)

如果在14行后面加入一個break，可以將插入排序進(jìn)行小小的優(yōu)化。

優(yōu)化的插入排序

只是減少了代碼量，并沒有化簡運算步驟

int j;for (i = 0; i < total; i++){for (j = i; j > 0 && a[j] < a[j - 1]; j--)//短路運算{SWAP(a[j], a[j - 1]);}}

測試用例
輸入

10
10 9 8 7 6 5 4 3 2 1

輸出

另一種插入方式：用temp臨時存放想要插入的元素，找到插入位置之后循環(huán)右移插入。

希爾排序

現(xiàn)在這個階段，一定不要小瞧任何基礎(chǔ)知識，記住自己永遠(yuǎn)是初學(xué)者。

在知乎上看到這樣的問題：

疑問：既然希爾排序是距離不斷縮小的插入排序，那為什么希爾排序不需要用到元素的循環(huán)右移？希爾排序的底層真的只是簡單的插入排序嗎？

普通的希爾排序：底層就是簡單的插入排序。最內(nèi)層for循環(huán)是元素的循環(huán)右移

代碼

自己寫的希爾排序，底層就是簡單的插入排序，用類似冒泡的方式實現(xiàn)的插入。

#include<iostream> using namespace std; #define SWAP(a,b) {int tmp;tmp=a;a=b;b=tmp;} int main() {int a[1000];//總數(shù)int total;cout << "請輸入排序的元素個數(shù)：";cin >> total;//輸入數(shù)據(jù)int i;cout << "請輸入要排序的數(shù)字：";for (i = 0; i < total; i++){cin >> a[i];}int gap, j;for (gap = total / 2; gap > 0; gap /= 2){//每一組分別執(zhí)行跨度為gap的插入排序for (int zu = 0; zu < gap; zu++){//組內(nèi)插入排序：類似于冒泡，就是把當(dāng)前希望插入的元素通過兩兩比較，左移到它應(yīng)該在的位置(讓他的左邊沒有比它小的元素)for (i = 0; i < total; i += gap){for (j = i; j - gap >= 0; j -= gap){if (a[j] < a[j - gap]){SWAP(a[j], a[j - 1]);}}}}//以下是高端版的希爾排序 沒看明白 但是正確運行//for (i = gap; i < total; i++)//i控制偏移量 決定當(dāng)前偏移量下的組號//{// for (j = i - gap; j >= 0; j -= gap)//j跨度為gap 組內(nèi)比較// {// if (a[j] > a[j + gap])//如果前大，則把后一項向前移動// {// SWAP(a[j], a[j + gap]);// break;// }// }//}}//輸出cout << "排序結(jié)果：\n";for (i = 0; i < total; i++){cout << a[i] << " ";}system("pause"); }

代碼2

void ShellSort(int array[], int length) {int d = length / 2; //設(shè)置希爾排序的增量int i;int j;int temp;while (d >= 1){for (i = d; i < length; i++){temp = array[i];j = i - d;while (j >= 0 && array[j] < temp){array[j + d] = array[j];j = j - d;}array[j + d] = temp;}d = d / 2; //縮小增量 } }

總結(jié)

以上是生活随笔為你收集整理的【排序算法】冒泡排序 选择排序 插入排序 希尔排序（数组）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。