八大经典排序（二）

直接选择排序:

在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素
若它不是这组元素中的最后一个(第一个)元素&＃xff0c;则将它与这组元素中的最后一个&＃xff08;第一个&＃xff09;元素交换在剩余的array[i]–array[n-2]&＃xff08;array[i&＃43;1]–array[n-1]&＃xff09;集合中&＃xff0c;重复上述步骤&＃xff0c;直到集合剩余1个元素

实现代码&＃xff1a;

void SelectSort(int *parray, int n)
{int begin &＃61; 0, end &＃61; n - 1;while (begin < end)//数组比较已经到中间位置已经确定了数组最大值最小值{for (int i &＃61; begin; i <&＃61; end; i&＃43;&＃43;)//当前数组没有确定的数组元素下标{if (parray[i] > parray[end]){Swap(&parray[i], &parray[end]);}else if (parray[i] < parray[begin]){Swap(&parray[i], &parray[begin]);}}begin&＃43;&＃43;, end--;//确定后下此数组的下标减少}
}

直接选择排序的特性总结&＃xff1a;

1. 直接选择排序思考非常好理解&＃xff0c;但是效率不是很好。实际中很少使用
2. 时间复杂度&＃xff1a;O(N^2)
3. 空间复杂度&＃xff1a;O(1)
4. 稳定性&＃xff1a;不稳定

堆排序

堆排序(Heapsort)是指利用堆积树&＃xff08;堆&＃xff09;这种数据结构所设计的一种排序算法&＃xff0c;它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆&＃xff0c;排降序建小堆。

重复继续调整结果为

实现代码&＃xff1a;

void AdjustHeapSort(int *a, int n, int parent)//向下调整算法
{assert(a);int child &＃61; parent * 2 &＃43; 1;//左孩子int temp &＃61; 0;while (child < n){if ((child &＃43; 1 < n) && a[child &＃43; 1] > a[child])//判断右孩子是否大于左孩子{&＃43;&＃43;child;}if (a[child]>a[parent])//将大的孩子与父亲交换{Swap(&a[child], &a[parent]);parent &＃61; child;child &＃61; parent * 2 &＃43; 1;}else{break;}}
}void HeapSort(int *a, int n)
{assert(a);//建大堆for (int i &＃61; (n - 2) / 2; i >&＃61; 0; i--){AdjustHeapSort(a, n, i);}//选数int end &＃61; n - 1;while (end>0){Swap(&a[end], &a[0]);AdjustHeapSort(a, end, 0);end--;}
}

直接选择排序的特性总结&＃xff1a;

1. 堆排序使用堆来选数&＃xff0c;效率就高了很多。
2. 时间复杂度&＃xff1a;O(N*logN)
3. 空间复杂度&＃xff1a;O(1)
4. 稳定性&＃xff1a;不稳定

冒泡排序

实现代码&＃xff1a;
两两比较相邻记录的关键字&＃xff0c;如果反序则交换&＃xff0c;直到没有反序的记录为止。冒泡的实现在细节上可以很多种变化&＃xff0c;我们就最简单的一种冒泡实现代码&＃xff0c;来讲解冒泡排序的思想。

void BubbleSort(int *parray, int n)
{int i &＃61; 0, t &＃61; 0;int flag &＃61; 0;for (i &＃61; 0; i < n; i&＃43;&＃43;){for (t &＃61; 1; t < n; t&＃43;&＃43;){if (parray[t - 1]>parray[t]){int p &＃61; 0;p &＃61; parray[t];parray[t] &＃61; parray[t - 1];parray[t - 1] &＃61; p;flag &＃61; 1;}}if (flag &＃61;&＃61; 0){break;}}
}


冒泡排序的特性总结&＃xff1a;

1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度&＃xff1a;O(N^2)
3. 空间复杂度&＃xff1a;O(1)
4. 稳定性&＃xff1a;稳定