以前也零零碎碎發(fā)過一些排序算法，但排版都不太好，又重新整理一次，排序算法是數(shù)據(jù)結(jié)構(gòu)的重要部分，系統(tǒng)地學(xué)習(xí)很有必要。
| 排序算法 | 平均時(shí)間復(fù)雜度 | 最差時(shí)間復(fù)雜度 | 空間復(fù)雜度 | 數(shù)據(jù)對(duì)象穩(wěn)定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n2) | O(n2) | O(1) | 穩(wěn)定 |
| 選擇排序 | O(n2) | O(n2) | O(1) | 數(shù)組不穩(wěn)定、鏈表穩(wěn)定 |
| 插入排序 | O(n2) | O(n2) | O(1) | 穩(wěn)定 |
| 快速排序 | O(n*log2n) | O(n2) | O(log2n) | 不穩(wěn)定 |
| 堆排序 | O(n*log2n) | O(n*log2n) | O(1) | 不穩(wěn)定 |
| 歸并排序 | O(n*log2n) | O(n*log2n) | O(n) | 穩(wěn)定 |
| 希爾排序 | O(n*log2n) | O(n2) | O(1) | 不穩(wěn)定 |
| 計(jì)數(shù)排序 | O(n+m) | O(n+m) | O(n+m) | 穩(wěn)定 |
| 桶排序 | O(n) | O(n) | O(m) | 穩(wěn)定 |
| 基數(shù)排序 | O(k*n) | O(n2) | 穩(wěn)定 |
算法思想：
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;
}
}
}
}
算法思想：
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;
}
算法思想：
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);
}
算法思想：
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);
}
堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。
算法思想：
#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;
}
歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為2-路歸并。
算法思想：1.把長(zhǎng)度為n的輸入序列分成兩個(gè)長(zhǎng)度為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ì)等長(zhǎng)的兩個(gè)子表合并
i = i+ len;
}
if(i + s < lenght){
Merge(q, rf, i, i+ s -1, lenght -1); //對(duì)不等長(zhǎng)的兩個(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);
}
希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進(jìn)版本。但希爾排序是非穩(wěn)定排序算法。先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序.
算法思想：
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;
}
}
計(jì)數(shù)排序統(tǒng)計(jì)小于等于該元素值的元素的個(gè)數(shù)i，于是該元素就放在目標(biāo)數(shù)組的索引i位（i≥0）。
算法思想：
#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;
}
將值為i的元素放入i號(hào)桶，最后依次把桶里的元素倒出來。
算法思想：
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;
}
一種多關(guān)鍵字的排序算法，可用桶排序?qū)崿F(xià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.
-END-
推薦閱讀
