C语言动图演示十大经典排序算法（附代码）

算法分析：插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为较新元素提供插入空间。4. 快速排序

快速排序的基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

算法思想：

（1）选取第一个数为基准

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

（3）递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序

代码：

void QuickSort(vector<int>& 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); 
}

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

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

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

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

代码：

#include 

#include 
using namespace std; 
// 堆排序：（较大堆，有序区）。从堆顶把根卸出来放在有序区之前，再恢复堆。 
void **x_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--) 
**x_heapify(arr, i, len - 1); 
//先将第一个元素和已经排好的元素前一位做交换，再从新调整(刚调整的元素之前的元素)，直到排序完成 
for (int i = len - 1; i > 0; i--) { 
swap(arr[0], arr); 

**x_heapify(arr, 0, i - 1); 
} 
} 
int **in() { 
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 << ' '; 

cout << endl; 
return 0; 
}

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]归并到辅助数组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) 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 ); //对等长的两个子表合并 
i = i+ len; 
} 
if(i + s < lenght){ 
Merge(q, rf, i, i+ s -1, lenght -1); //对不等长的两个子表合并 
} 
tmp = q; q = rf; rf = tmp; //交换q,rf，以保证下一趟归并时，仍从q 归并到rf 
} 
} 
int **in(){ 
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<<"结果："; 
print(a,10); 
}</lenght){

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

#include 

#include 
#include 
using namespace std; 
// 计数排序 
void CountSort(vector<int>& vecRaw, vector<int>& vecObj) 
{ 
// 确保待排序容器非空 
if (vecRaw.size() == 0) 
return; 
// 使用 vecRaw 的较大值 + 1 作为计数容器 countVec 的大小 
int vecCountLength = (***x_element(begin(vecRaw), end(vecRaw))) + 1; 
vector<int> vecCount(vecCountLength, 0); 
// 统计每个键值出现的次数 
for (int i = 0; i < vecRaw.size(); i++) 
vecCount[vecRaw]++; 

// 后面的键值出现的位置为前面所有键值出现的次数之和 
for (int i = 1; i < vecCountLength; i++) 
vecCount += vecCount[i - 1]; 

// 将键值放到目标位置 
for (int i = vecRaw.size(); i > 0; i--) // 此处逆序是为了保持相同键值的稳定性 
vecObj[--vecCount[vecRaw[i - 1]]] = vecRaw[i - 1]; 
} 
int **in() 
{ 
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 << " "; 

cout << endl; 
return 0; 
}

void Bucket_Sort(int a[], int n, int **x) { 

int i, j=0; 
int *buckets = (int*)**lloc((**x+1)*sizeof(int)); 
// 将buckets中的所有数据都初始化为0 
memset(buckets, 0, (**x+1) * sizeof(int)); 
// 1.计数 
for (i = 0; i < n; i++) { 
buckets[a]++; 

printf("%d : %d\n", a, buckets[a]); 

} 
printf("\n"); 
// 2.排序 
for (i = 0; i < **x+1; i++) { 
while ((buckets--) > 0) { 

a[j++] = i; 
} 
} 
} 
int **in() { 
int arr[] = { 9,5,1,6,2,3,0,4,8,7 }; 
Bucket_Sort(arr, 10,9); 
for (int i = 0; i < 10; i++) { 
printf("%d ", arr); 

} 
printf("\n"); 
return 0; 
}

int **xbit(int data[], int n) //辅助函数，求数据的较大位数 

{ 
int **xData = data[0]; ///< 较大数 
/// 先求出较大数，再求其位数，这样有原先依次每个数判断其位数，稍微优化点。 
for (int i = 1; i < n; ++i) 
{ 
if (**xData < data) 

**xData = data; 

} 
int d = 1; 
int p = 10; 
while (**xData >= p) 
{ 
//p *= 10; // Maybe overflow 
**xData /= 10; 
++d; 
} 
return d; 
/* int d = 1; //保存较大的位数 
int p = 10; 
for(int i = 0; i < n; ++i) 
{ 
while(data >= p) 

{ 
p *= 10; 
++d; 
} 
} 
return d;*/ 
} 
void radixsort(int data[], int n) //基数排序 
{ 
int d = **xbit(data, n); 
int *tmp = new int[n]; 
int *count = new int[10]; //计数器 
int i, j, k; 
int radix = 1; 
for(i = 1; i <= d; i++) //进行d次排序 
{ 
for(j = 0; j < 10; j++) 
count[j] = 0; //每次分配前清空计数器 
for(j = 0; j < n; j++) 
{ 
k = (data[j] / radix) % 10; //统计每个桶中的记录数 
count[k]++; 
} 
for(j = 1; j < 10; j++) 
count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶 
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++) //将临时数组的内容**到data中 
data[j] = tmp[j]; 
radix = radix * 10; 
} 
delete []tmp; 
delete []count; 
}