c 语言从大到小排序算法 10 大经典排序算法（动图演示+ C 语言代码）

原标题：10 大经典排序算法(动图演示+ C 语言代码)

来源：C语言与CPP编程

以前也零零碎碎发过一些排序算法，但排版都不太好，又重新整理一次，排序算法是数据结构的重要部分，系统地学习很有必要。

时间、空间复杂度比较

排序算法

平均时间复杂度

最差时间复杂度

空间复杂度

数据对象稳定性

冒泡排序

O(n2)

O(n2)

O(1)

稳定

选择排序

O(n2)

O(n2)

O(1)

数组不稳定、链表稳定

插入排序

O(n2)

O(n2)

O(1)

稳定

快速排序

O(n*log2n)

O(n2)

O(log2n)

不稳定

堆排序

O(n*log2n)

O(n*log2n)

O(1)

不稳定

归并排序

O(n*log2n)

O(n*log2n)

O(n)

稳定

希尔排序

O(n*log2n)

O(n2)

O(1)

不稳定

计数排序

O(n+m)

O(n+m)

O(n+m)

稳定

桶排序

O(n)

O(n)

O(m)

稳定

基数排序

O(k*n)

O(n2)

稳定

1 冒泡排序

算法思想：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

冒泡排序动图演示代码：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;

}

}

}

}

2 选择排序

算法思想：

在未排序序列中找到最小(大)元素，存放到排序序列的起始位置

从剩余未排序元素中继续寻找最小(大)元素，然后放到已排序序列的末尾

以此类推，直到所有元素均排序完毕

选择排序动图演示代码：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]) { // 寻找最小的数

minIndex = j; // 将最小数的索引保存

}

}

temp = arr[i];

arr[i] = arr[minIndex];

arr[minIndex] = temp;

}

return arr;

}

3 插入排序

算法思想：

从第一个元素开始，该元素可以认为已经被排序

取出下一个元素，在已经排序的元素序列中从后向前扫描

如果该元素(已排序)大于新元素，将该元素移到下一位置

重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

将新元素插入到该位置后

重复步骤2~5

插入排序动图演示代码：void print(int a[], int n ,int i){

cout<

for(int j= 0; j<8; j++){

cout<

}

cout<

}

void InsertSort(int a[], int n)

{

for(int i= 1; i

if(a[i] < a[i-1]){ //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入

int j= i-1;

int x = a[i]; //复制为哨兵，即存储待排序元素

a[i] = a[i-1]; //先后移一个元素

while(x < a[j]){ //查找在有序表的插入位置

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

j--; //元素后移

}

a[j+1] = x; //插入到正确位置

}

print(a,n,i); //打印每趟排序的结果

}

}

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);

}

4 快速排序

算法思想：

选取第一个数为基准

将比基准小的数交换到前面，比基准大的数交换到后面

对左右区间重复第二步，直到各区间只有一个数

快速排序动图演示代码：void QuickSort(vector& v, int low, int high) {

if (low >= high)// 结束标志

return;

int first = low;// 低位下标

int last = high;// 高位下标

int key = v[first];// 设第一个为基准

while (first < last)

{

// 将比第一个小的移到前面

while (first < last && v[last] >= key)

last--;

if (first < last)

v[first++] = v[last];

// 将比第一个大的移到后面

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);

}

5 堆排序

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于(或者大于)它的父节点。

算法思想：

将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；

将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；

由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

代码：#include

#include

using namespace std;

// 堆排序：(最大堆，有序区)。从堆顶把根卸出来放在有序区之前，再恢复堆。

void max_heapify(int arr[], int start, int end) {

//建立父节点指标和子节点指标

int dad = start;

int son = dad * 2 + 1;

while (son <= end) { //若子节点在范围内才做比较

if (son + 1 <= end && arr[son] < arr[son + 1]) //先比较两个子节点指标，选择最大的

son++;

if (arr[dad] > arr[son]) //如果父节点大于子节点代表调整完成，直接跳出函数

return;

else { //否则交换父子內容再继续子节点与孙节点比較

swap(arr[dad], arr[son]);

dad = son;

son = dad * 2 + 1;

}

}

}

void heap_sort(int arr[], int len) {

//初始化，i从最后一个父节点开始调整

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

max_heapify(arr, i, len - 1);

//先将第一个元素和已经排好的元素前一位做交换，再从新调整(刚调整的元素之前的元素)，直到排序完成

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;

}

6 归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

算法思想：1.把长度为n的输入序列分成两个长度为n/2的子序列；2. 对这两个子序列分别采用归并排序；3. 将两个排序好的子序列合并成一个最终的排序序列。

归并排序动图演示代码：void print(int a[], int n){

for(int j= 0; j

cout<