1. 插入排序
1. 直接插入排序
void XYInsertSort::sorted(int *arr)
{
int sentry;
for (int i = 1; i < arrCount; i++) {
sentry = arr[i];
int j = i - 1;
for (j = i - 1; j >= 0; j--) {
if (sentry < arr[j]) {
arr[j + 1] = arr[j];
}else{
break;
}
}
arr[j + 1] = sentry;
}
}
最好情况：顺序 T = O(n)
最坏情况：逆序 T = O(n2)
直接插入排序算法简便，当待排数据数量n很小时，这是一个很好的排序方法。但是通常待排数据数量n很大。因此直接插入排序就不适用了。
2. 折半插入排序
- 由于插入排序是在一个有序的数据中查找和插入，因此我们可以用折半比较的方式确定插入位置。
void XYBInsertSort::sorted(int *arr)
{
int sentry, low, height, mid;
for (int i = 1; i < arrCount; i++) {
sentry = arr[i];
low = 0;
height = i - 1;
while (low <= height) {
mid = (low + height) / 2;
if (sentry < arr[mid]) {
height = mid - 1;
}else if (sentry > arr[mid]){
low = mid + 1;
}else{
low = mid + 1;
break;
}
}
for (int j = i - 1; j >= low; j--) {
arr[j + 1] = arr[j];
}
arr[low] = sentry;
}
}
折半插入排序仅减少了关键字间的比较次数，而记录移动次数不变，因此，折半插入排序的时间复杂度仍为O(n2)。
3. 2-路插入排序
2-路插入排序在折半插入排序的基础上再改进之，其目的是减少排序过程中的移动次数，但需要添加n的辅助空间。我们添加一个数组arrB,并将其看做循环链表，并设置两个指针first和fianl分别指向第一个记录和最后一个记录。
先拿arrA中的元素跟arrB[first]进行比较,如果小于arrB[first]，则插入到arrB[first]前面。否则再与arrB[final]比较，如果大于arrB[final]出入到其后面。否则，直接插入法插入到first和final中间的位置。
//二路插入排序
void XYTwInsertSort::sorted(int *arr)
{
int *arrB = (int*)malloc(sizeof(int) * arrCount);
arrB[0] = arr[0];
int first = 0, last = 0;
for (int i = 1; i < arrCount; i++) {
if(arr[i] < arrB[first])
{
first = (first - 1 + arrCount) % arrCount;
arrB[first] = arr[i];
}else if (arr[i] > arrB[last]){
last++;
arrB[last] = arr[i];
}else{
last++;
arrB[last] = arrB[last - 1];
int j = last - 1;
for(;arr[i] < arrB[(j - 1 + arrCount) % arrCount]; j = (j - 1 + arrCount) % arrCount){
arrB[j] = arrB[(j - 1 + arrCount) % arrCount];
}
arrB[j] = arr[i];
}
}
for (int k = 0; k < arrCount; k++) {
arr[k] = arrB[first];
first = (first + 1) % arrCount;
}
}
4. 表插入排序
理解了之前的2-路插入排序算法之后，再此详解表插入排序:折半插入排序相比于直接插入排序减少了比较的次数;·2-路插入排序相比于折半插入排序减少了移动的次数;
- 表插入排序则是在排序过程中不移动记录，只改变存储结构，进行表插入排序的过程;
- 具体做法:使用静态链表类型作为待排记录序列的存储结构，并且设置数组下标为0的分量为头结点。
- 第一步:将静态链表中数组下标为1的分量和表头节点构成一个循环链表，然后依次将下标为2到n的分量按记录的关键字非递减有序插入到循环链表中。
void XYTableInsertSort::sorted(int *arr)
{
table[0].next = 1;
//当前位置
int index;
//前驱
int pre;
for (int i = 2; i < arrCount + 1; i++) {
index = table[0].next;
pre = 0;
while (index!=0 && table[i].data >= table[index].data) {
pre = index;
index = table[index].next;
}
//当到达表尾或table[i].data < table[index].data时，插入到index之前
table[i].next = index;
//修改前驱的指向
table[pre].next = i;
}
//遍历表存入到num_p数组中
int curTableIndex = table[0].next;
for(int i = 0; i< arrCount; i++)
{
arr[i] = table[curTableIndex].data;
curTableIndex = table[curTableIndex].next;
}
}
- 从表插入排序的过程可以看到，表插入排序的基本操作还是将一个记录插入到已排好序的有序表中;
- 表插入排序和直接插入排序相比，不同之处是仅以修改2n次指针代替记录的移动，排序过程中所需进行的关键字之间的比较次数相同，所以表插入排序的时间复杂度是O(n2);
- 表插入排序的结果只是求得一个有序链表(静态)，则只能对进行顺序查找，而不能进行随机查找，如果要实现折半之类的查找，则需要对记录进行重排。
2. 希尔排序
希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。
void XYShellSort::sorted(int *arr)
{
int dk = arrCount / 2 + 1;
int sentry;
while (dk > 0) {
for (int i = dk; i < arrCount; i++) {
sentry = arr[i];
int j;
for ( j = i - dk; j >= 0; j -= dk) {
if (sentry < arr[j]) {
arr[j + dk] = arr[j];
}else{
break;
}
}
arr[j + dk] = sentry;
}
dk /= 2;
}
}
- 希尔排序是基于插入排序的一种算法， 在此算法基础之上增加了一个新的特性，提高了效率。希尔排序的时间的时间复杂度为O(n3/2)，希尔排序时间复杂度的下界是n*log2n
3. 快速排序
1. 冒泡排序
int * XYBubblingSort::sorted(int *arr)
{
for (int i = 0; i < arrCount - 1; i++) {
for (int j = 0; j < arrCount - 1 - i ; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
- 冒泡排序的时间复杂度为T = O(n2)
冒泡排序的优化
当某趟比较不再交换时，说明已经有序，就没必要继续比较了。
int * XYBubblingSort::sorted2(int *arr)
{
for (int i = 0; i < arrCount - 1; i++) {
bool flag = true;
for (int j = 0; j < arrCount - 1 - i ; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = false;
}
}
if(flag)
break;
}
return arr;
}
快速排序(Quick Sort):是对冒泡排序的一种改进。它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可以分别对这两部分记录继续进行排序，以达到整个序列有序。
void XYQuickSort::sorted(int *arr, int low, int height)
{
if (low < height) {
int pivotloc= partition(arr, low, height);
sorted(arr, low, pivotloc - 1);
sorted(arr, pivotloc + 1, height);
}
}
int XYQuickSort::partition(int *arr, int low, int height)
{
int sentry = arr[low], temp;
while (low < height) {
while (low < height && sentry <= arr[height]) {
height--;
}
temp = arr[height];
arr[height] = sentry;
arr[low] = temp;
while (low < height && sentry >= arr[low]) {
low++;
}
temp = arr[low];
arr[low] = sentry;
arr[height] = temp;
}
return low;
}
- 快速排序的平均时间复杂度和最坏时间复杂度分别是O(nlgn)、O(n2)。
4. 选择排序
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
void XYSelectSort::sorted(int *arr)
{
int min, minIndex, temp;
for (int i = 0; i < arrCount - 1; i++) {
min = arr[i];
minIndex = i;
for (int j = i + 1; j < arrCount; j++) {
if (arr[j] < min ) {
min = arr[j];
minIndex = j;
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
5. 堆排序
- 咱们前面已经讲解了堆，堆排序的方法是删除堆返回最大堆的最大值或最小堆的最小值，从而实现堆排序。
- 堆排序的时间复杂度 T = O(nlogn)
最大堆排序
void MaxHeapSort(MaxHeap h)
{
printf("堆排序：");
for (int i = 1; i <= h->capacity; i++) {
ElementType item = deleteMax(h);
printf("%d ",item);
}
}
