冒泡排序图解
[48, 12, 52, 36, 5] 第1趟排序
[48, 12, 52, 36, 5] 第2趟排序
[48, 12, 52, 36, 5] 第3趟排序
[48, 12, 52, 36, 5] 第4趟排序
快速排序图解
image.png
image.png
image.png
image.png
image.png
image.png
选择排序图解
image.png
堆排序
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
void HeapAdjust(int* arr, int start, int end)
{
int tmp = arr[start];
for (int i = 2 * start + 1; i <= end; i = i * 2 + 1)
{
if (i < end&& arr[i] < arr[i + 1])//有右孩子并且左孩子小于右孩子
{
i++;
}//i一定是左右孩子的最大值
if (arr[i] > tmp)
{
arr[start] = arr[i];
start = i;
}
else
{
break;
}
}
arr[start] = tmp;
}
void HeapSort(int* arr, int len)
{
//第一次建立大根堆，从后往前依次调整
for(int i=(len-1-1)/2;i>=0;i--)
{
HeapAdjust(arr, i, len - 1);
}
//每次将根和待排序的最后一次交换，然后在调整
int tmp;
for (int i = 0; i < len - 1; i++)
{
tmp = arr[0];
arr[0] = arr[len - 1-i];
arr[len - 1 - i] = tmp;
HeapAdjust(arr, 0, len - 1-i- 1);
}
}
int main()
{
int arr[] = { 9,5,6,3,5,3,1,0,96,66 };
HeapSort(arr, sizeof(arr) / sizeof(arr[0]));
printf("排序后为:");
for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
{
printf("%d ", arr[i]);
}
return 0;
}
1 //堆排序
2 /*
3 大顶堆sort之后，数组为从小到大排序
4 */
5 //====调整=====
6 void AdjustHeap(int* h, int node, int len) //----node为需要调整的结点编号，从0开始编号;len为堆长度
7 {
8 int index=node;
9 int child=2*index+1; //左孩子，第一个节点编号为0
10 while(child<len)
11 {
12 //右子树
13 if(child+1<len && h[child]<h[child+1])
14 {
15 child++;
16 }
17 if(h[index]>=h[child]) break;
18 Swap(h[index],h[child]);
19 index=child;
20 child=2*index+1;
21 }
22 }
23
24
25 //====建堆=====
26 void MakeHeap(int* h, int len)
27 {
28 for(int i=len/2;i>=0;--i)
29 {
30 AdjustHeap(h, i, len);
31 }
32 }
33
34 //====排序=====
35 void HeapSort(int* h, int len)
36 {
37 MakeHeap(h, len);
38 for(int i=len-1;i>=0;--i)
39 {
40 Swap(h[i],h[0]);
41 AdjustHeap(h, 0, i);
42 }
43 }
