一领斥、選擇排序
選擇排序（Selection Sort）是一種簡(jiǎn)單直觀的排序算法。它的工作原理如下梦湘，首先在未排序序列中找到最邢箍拧（大）元素件甥，存放到排序序列的起始位置，然后哼拔，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最幸小（大）元素，然后放到已排序序列的末尾倦逐。以此類推轿曙，直到所有元素均排序完畢。下面用圖片來(lái)說(shuō)明一下這個(gè)算法：
首先我們先找到數(shù)組中最小的元素
然后將找到的最小元素與數(shù)組的第一個(gè)元素交換位置
這樣我們的數(shù)組中的第一個(gè)元素就是已經(jīng)排好序的僻孝，然后我們找數(shù)組中除去第一個(gè)元素外最小的元素
將找到的元素與第二個(gè)元素交換导帝，這時(shí)我們數(shù)組的前兩個(gè)元素是排序好的元素
依次按照前面的方法操作
最終得到完全排好序的數(shù)組
代碼如下：
#include<iostream>
#include<algorithm>
using namespace std;
void selectionSort(int arr[], int n) {
for(int i=0;i<n;i++) {
//尋找[i,n)區(qū)間中的最小值
int minIndex = i;
for(int j=i+1;j<n;j++) {
if(arr[j] < arr[minIndex]) minIndex= j;
}
swap(arr[i], arr[minIndex]);
}
}
int main() {
int a[10] = {10,9,8,7,2,3,4,6,5,1};
selectionSort(a, 10);
for(int i=0;i<10;i++) {
cout<<a[i]<<" ";
}
cout<<endl;
return 0;
}
二、插入排序
設(shè)有一組關(guān)鍵字｛K1穿铆， K2您单，…， Kn｝荞雏；排序開始就認(rèn)為 K1 是一個(gè)有序序列虐秦；讓 K2 插入上述表長(zhǎng)為 1 的有序序列，使之成為一個(gè)表長(zhǎng)為 2 的有序序列凤优；然后讓 K3 插入上述表長(zhǎng)為 2 的有序序列悦陋，使之成為一個(gè)表長(zhǎng)為 3 的有序序列；依次類推筑辨，最后讓 Kn 插入上述表長(zhǎng)為 n-1 的有序序列俺驶，得一個(gè)表長(zhǎng)為 n 的有序序列。下面用圖片來(lái)說(shuō)明一下這個(gè)算法：
默認(rèn)數(shù)組的第一個(gè)元素是已經(jīng)排好序的棍辕，所以這里從第二個(gè)元素開始
將第二各元素插入到已經(jīng)排序的元素中（這里只有第一個(gè)暮现，所以我們將第二個(gè)元素和第一個(gè)元素交換位置），接下來(lái)我們看第三個(gè)元素
依次將第三個(gè)元素與前面兩個(gè)已排序元素比較楚昭，如果小于已排序元素栖袋，就交換位置，實(shí)現(xiàn)插入的效果
接著重復(fù)上面的操作抚太，直到數(shù)組變?yōu)橛行虻臑橹?/strong>
代碼如下：
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
void insertionsort(int arr[], int n) {
for(int i=1;i<n;i++) {
//尋找元素arr[i]合適的插入位置
for(int j=i;j>0;j--) {
if(arr[j] < arr[j-1]) {
swap(arr[j], arr[j-1]);
}
else {
break;
}
}
}
}
int main() {
int a[10] = {10,9,8,7,2,3,4,6,5,1};
insertionsort(a, 10);
for(int i=0;i<10;i++) {
cout<<a[i]<<" ";
}
cout<<endl;
return 0;
}
三塘幅、優(yōu)化插入排序
我們可以發(fā)現(xiàn)上面的插入排序?qū)崿F(xiàn)其實(shí)是有問(wèn)題的，我們其實(shí)沒有必要將插入的元素與已排序的元素一一進(jìn)行替換尿贫，我們只需要找到要插入的位置电媳，然后將后面的元素都后移一位就可以了。優(yōu)化后的代碼如下：
void insertionsort2(int arr[], int n) {
for(int i=1;i<n;i++) {
//尋找元素arr[i]合適的插入位置
int t = arr[i];
int j;//保存元素t應(yīng)該插入的位置
for(j=i;j>0;j--) {
if(arr[j-1] > t) {
arr[j] = arr[j-1];
}
else {
break;
}
}
arr[j] = t;
}
}
四帅霜、冒泡排序
冒泡排序（Bubble Sort匆背，臺(tái)灣譯為：泡沫排序或氣泡排序）是一種簡(jiǎn)單的排序算法。它重復(fù)地走訪過(guò)要排序的數(shù)列身冀，一次比較兩個(gè)元素钝尸，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換搂根，也就是說(shuō)該數(shù)列已經(jīng)排序完成珍促。這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。下面用圖片來(lái)說(shuō)明一下這個(gè)算法：
代碼實(shí)現(xiàn)：
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
void bubble_sort(int arr[], int len) {
int i, j;
for (i = 0; i < len - 1; i++)
for (j = 0; j < len - 1 - i; j++)
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
int main() {
int a[10] = {10,9,8,7,2,3,4,6,5,1};
bubble_sort(a, 10);
for(int i=0;i<10;i++) {
cout<<a[i]<<" ";
}
cout<<endl;
return 0;
}
