C++實現八個常用的排序算法：插入排序、冒泡排序、選擇排序、希爾排序等

2020-05-23 14:16:37

字體：大中小

來源：轉載

供稿：網友

這篇文章主要介紹了C++如何實現八個常用的排序算法：插入排序、冒泡排序、選擇排序、希爾排序、快速排序、歸并排序、堆排序和LST基數排序,需要的朋友可以參考下

本文實現了八個常用的排序算法：插入排序、冒泡排序、選擇排序、希爾排序、快速排序、歸并排序、堆排序和LST基數排序

算法實現文件Sort.h

首先是，代碼如下：

/*

* 實現了八個常用的排序算法：插入排序、冒泡排序、選擇排序、希爾排序

* 以及快速排序、歸并排序、堆排序和LST基數排序

* @author gkh178

*/

#include <iostream>

template<class T>

void swap_value(T &a, T &b)

{

T temp = a;

a = b;

b = temp;

}

//插入排序：時間復雜度o(n^2)

template<class T>

void insert_sort(T a[], int n)

{

for (int i = 1; i < n; ++i)

{

T temp = a[i];

int j = i - 1;

while (j >= 0 && a[j] > temp)

{

a[j + 1] = a[j];

--j;

}

a[j + 1] = temp;

}

}

//冒泡排序：時間復雜度o(n^2)

template<class T>

void bubble_sort(T a[], int n)

{

for (int i = n - 1; i > 0; --i)

{

for (int j = 0; j < i; ++j)

{

if (a[j] > a[j + 1])

{

swap_value(a[j], a[j + 1]);

}

}

}

}

//選擇排序：時間復雜度o(n^2)

template<class T>

void select_sort(T a[], int n)

{

for (int i = 0; i < n - 1; ++i)

{

T min = a[i];

int index = i;

for (int j = i + 1; j < n; ++j)

{

if (a[j] < min)

{

min = a[j];

index = j;

}

}

a[index] = a[i];

a[i] = min;

}

}

//希爾排序：時間復雜度介于o(n^2)和o(nlgn)之間

template<class T>

void shell_sort(T a[], int n)

{

for (int gap = n / 2; gap >= 1; gap /= 2)

{

for (int i = gap; i < n; ++i)

{

T temp = a[i];

int j = i - gap;

while (j >= 0 && a[j] > temp)

{

a[j + gap] = a[j];

j -= gap;

}

a[j + gap] = temp;

}

}

}

//快速排序：時間復雜度o(nlgn)

template<class T>

void quick_sort(T a[], int n)

{

_quick_sort(a, 0, n - 1);

}

template<class T>

void _quick_sort(T a[], int left, int right)

{

if (left < right)

{

int q = _partition(a, left, right);

_quick_sort(a, left, q - 1);

_quick_sort(a, q + 1, right);

}

}

template<class T>

int _partition(T a[], int left, int right)

{

T pivot = a[left];

while (left < right)

{

while (left < right && a[right] >= pivot)

{

--right;

}

a[left] = a[right];

while (left < right && a[left] <= pivot)

{

++left;

}

a[right] = a[left];

}

a[left] = pivot;

return left;

}

//歸并排序：時間復雜度o(nlgn)

template<class T>

void merge_sort(T a[], int n)

{

_merge_sort(a, 0, n - 1);

}

template<class T>

void _merge_sort(T a[], int left, int right)

{

if (left < right)

{

int mid = left + (right - left) / 2;

_merge_sort(a, left, mid);

_merge_sort(a, mid + 1, right);

_merge(a, left, mid, right);

}

}

template<class T>

void _merge(T a[], int left, int mid, int right)

{

int length = right - left + 1;

T *newA = new T[length];

for (int i = 0, j = left; i <= length - 1; ++i, ++j)

{

*(newA + i) = a[j];

}

int i = 0;

int j = mid - left + 1;

int k = left;

for (; i <= mid - left && j <= length - 1; ++k)

{

if (*(newA + i) < *(newA + j))

{

a[k] = *(newA + i);

++i;

}

else

{

a[k] = *(newA + j);

++j;

}

}

while (i <= mid - left)

{

a[k++] = *(newA + i);

++i;

}

while (j <= right - left)

{

a[k++] = *(newA + j);

++j;

}

delete newA;

}

//堆排序：時間復雜度o(nlgn)

template<class T>

void heap_sort(T a[], int n)

{

built_max_heap(a, n);//建立初始大根堆

//交換首尾元素，并對交換后排除尾元素的數組進行一次上調整

for (int i = n - 1; i >= 1; --i)

{

swap_value(a[0], a[i]);

up_adjust(a, i);

}

}

//建立一個長度為n的大根堆

template<class T>

void built_max_heap(T a[], int n)

{

up_adjust(a, n);

}

//對長度為n的數組進行一次上調整

template<class T>

void up_adjust(T a[], int n)

{

//對每個帶有子女節點的元素遍歷處理，從后到根節點位置

for (int i = n / 2; i >= 1; --i)

{

adjust_node(a, n, i);

}

}

//調整序號為i的節點的值

template<class T>

void adjust_node(T a[], int n, int i)

{

//節點有左右孩子

if (2 * i + 1 <= n)

{

//右孩子的值大于節點的值，交換它們

if (a[2 * i] > a[i - 1])

{

swap_value(a[2 * i], a[i - 1]);

}

//左孩子的值大于節點的值，交換它們

if (a[2 * i - 1] > a[i - 1])

{

swap_value(a[2 * i - 1], a[i - 1]);

}

//對節點的左右孩子的根節點進行調整

adjust_node(a, n, 2 * i);

adjust_node(a, n, 2 * i + 1);

}

//節點只有左孩子，為最后一個有左右孩子的節點

else if (2 * i == n)

{

//左孩子的值大于節點的值，交換它們

if (a[2 * i - 1] > a[i - 1])

{

swap_value(a[2 * i - 1], a[i - 1]);

}

}

}

//基數排序的時間復雜度為o(distance(n+radix)),distance為位數，n為數組個數，radix為基數

//本方法是用LST方法進行基數排序，MST方法不包含在內

//其中參數radix為基數，一般為10；distance表示待排序的數組的數字最長的位數；n為數組的長度

template<class T>

void lst_radix_sort(T a[], int n, int radix, int distance)

{

T* newA = new T[n];//用于暫存數組

int* count = new int[radix];//用于計數排序，保存的是當前位的值為0 到 radix-1的元素出現的的個數

int divide = 1;

//從倒數第一位處理到第一位

for (int i = 0; i < distance; ++i)

{

//待排數組拷貝到newA數組中

for (int j = 0; j < n; ++j)

{

*(newA + j) = a[j];

}

//將計數數組置0

for (int j = 0; j < radix; ++j)

{

*(count + j) = 0;

}

for (int j = 0; j < n; ++j)

{

int radixKey = (*(newA + j) / divide) % radix; //得到數組元素的當前處理位的值

(*(count + radixKey))++;

}

//此時count[]中每個元素保存的是radixKey位出現的次數

//計算每個radixKey在數組中的結束位置，位置序號范圍為1-n

for (int j = 1; j < radix; ++j)

{

*(count + j) = *(count + j) + *(count + j - 1);

}

//運用計數排序的原理實現一次排序，排序后的數組輸出到a[]

for (int j = n - 1; j >= 0; --j)

{

int radixKey = (*(newA + j) / divide) % radix;

a[*(count + radixKey) - 1] = newA[j];

--(*(count + radixKey));

}

divide = divide * radix;

}

}

測試文件main.cpp

然后是，代碼如下：

#include "Sort.h"

using namespace std;

template<class T>

void printArray(T a[], int n)

{

for (int i = 0; i < n; ++i)

{

cout << a[i] << " ";

}

cout << endl;

}

int main()

{

for (int i = 1; i <= 8; ++i)

{

int arr[] = { 45, 38, 26, 77, 128, 38, 25, 444, 61, 153, 9999, 1012, 43, 128 };

switch (i)

{

case 1:

insert_sort(arr, sizeof(arr) / sizeof(arr[0]));

break;

case 2:

bubble_sort(arr, sizeof(arr) / sizeof(arr[0]));

break;

case 3:

select_sort(arr, sizeof(arr) / sizeof(arr[0]));

break;

case 4:

shell_sort(arr, sizeof(arr) / sizeof(arr[0]));

break;

case 5:

quick_sort(arr, sizeof(arr) / sizeof(arr[0]));

break;

case 6:

merge_sort(arr, sizeof(arr) / sizeof(arr[0]));

break;

case 7:

heap_sort(arr, sizeof(arr) / sizeof(arr[0]));

break;

case 8:

lst_radix_sort(arr, sizeof(arr) / sizeof(arr[0]), 10, 4);

break;

default:

break;

}

printArray(arr, sizeof(arr) / sizeof(arr[0]));

}

return 0;

}