数据结构之排序算法

目录

1. 插入排序

1.1.1 直接插入排序代码实现

1.1.2 直接插入排序的特性总结

1.2.1 希尔排序的实现

1.2.2 希尔排序的特性总结

2. 选择排序

2.1.1 选择排序

2.1.2 选择排序特性

2.2.1 堆排序

2.2.2 堆排序特性

3. 交换排序

3.1.1 冒泡排序

3.1.2 冒泡排序的特性

3.2.1 快速排序

3.2.1.1 hoare版本

3.2.1.2 挖坑法

3.2.1.3 前后指针法

3.2.2.1 快排的递归实现及优化

3.2.2.2 快排的非递归实现

3.2.2 快速排序的特性

4. 归并排序

4.1 归并递归实现

4.2 归并非递归实现

5. 非比较排序

5.1 计数排序

5.2 基数排序

5.3 桶排序

6. 排序算法复杂度及稳定性

---

1. 插入排序

1.1.1 直接插入排序代码实现

插入排序动图如下：

思想就是把[0,end]区间变为有序让后把下一个数据进行插入下面是代码实现：

我们先写一趟排序

int end ;
int tem = a[end + 1];
while (end >= 0)
{if (tem < a[end]){a[end + 1] = a[end];end--;}else{break;}
}
a[end + 1] = tem;

之后我们用一个for循环控制end的值就可以了

完整代码如下所示：

void InsertSort(int* a, int n)
{for (int i = 0; i < n - 1; i++){int end = i;int tem = a[end + 1];while (end >= 0){if (tem < a[end]){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tem;}
}

1.1.2 直接插入排序的特性总结

1. 元素集合越接近有序，直接插入排序算法的时间效率越高

2. 时间复杂度： O(N^2)

3. 空间复杂度： O(1) ，它是一种稳定的排序算法

4. 稳定性：稳定

1.2.1 希尔排序的实现

希尔排序法又称缩小增量法。希尔排序法的基本思想是： 先选定一个整数gap，把待排序文件中所有记录分成个 组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工

作。当到达 =1 时，所有记录在统一组内排好序 。

相距为gap的数为一组这样就可以分为gap组如下所示：这里以gap为3为例

如下图所示：

这里我解释一下为啥gap是多少就可以分为几组因为每组的起始位置依次加一而他们相聚gap所以就是gap组。

下面我们先进行一组排序代码如下：

void shellsort(int* a, int n)
{int gap = 3;for (int i = 0; i < n - gap; i += gap){int end = i;int key = a[end + gap];while (end >= 0){if (key < a[end]){a[end + gap] = a[end];end--;}else{break;}}a[end + gap] = key;}}

下面我们控制组数每组的开头是不一样的最后控制gap只有gap为1时是最后一趟排序其余的都是预排序完整代码如下：

void shellsort(int* a, int n)
{int gap = n;while (gap>1){gap = gap / 3 + 1;for (int j = 0; j < gap; j++){for (int i = j; i < n - gap; i += gap){int end = i;int key = a[end + gap];while (end >= 0){if (key < a[end]){a[end + gap] = a[end];end-=gap;}else{break;}}a[end + gap] = key;}}}
}

下面是另一种写法两种写法的效率是一样的第二种写法就是进行一组两个数据的插入后直接进行下一组

就是先4,2然后1,1然后3,8；第一种是一组全部弄完后再弄下一组两者的效率一样的

第二种代码如下：

void shellsort(int* a, int n)
{int gap = n;while (gap>1){gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++){int end = i;int key = a[end + gap];while (end >= 0){if (key < a[end]){a[end + gap] = a[end];end-=gap;}else{break;}}a[end + gap] = key;}}
}

1.2.2 希尔排序的特性总结

1. 希尔排序是对直接插入排序的优化。

2. 当 gap > 1 时都是预排序，目的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，这样就

会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

3. 希尔排序的时间复杂度不好计算，因为 gap 的取值方法很多，导致很难去计算，因此在好些树中给出的

希尔排序的时间复杂度都不固定

《数据结构(C语言版)》--严蔚敏
希尔排序的分析是一个复杂的问题,因为它的时间是所取"增量"序列的函数,这涉及
些数学上尚未解决的难题。因此,到目前为止尚未有人求得一种最好的增量序列,但大
量的研究已得出一些局部的结论。如有人指出,当增量序列为dIta[k]=25-6+1-1时,希
尔排序的时间复杂度为O(12312)其中t为排序趙数,1<k<t<log2(n+1)」。还有人在
大量的实验基础上推出
当刀在某个特定范围内,希尔排序所需的比较和移动次数为为
n1.3,当770时,可减少到7(10g27)201。增量序列可以有各种取法1,且需注意:应使增
量序列中的值没有除1之外的公因子,并且最后一个增量值必须等于1。
《数据结构-用面相对象方法与C++描述》---殷人昆

因为咋们的 gap 是按照 Knuth 提出的方式取值的，而且 Knuth 进行了大量的试验统计，我们暂时就按照：

到

来算。

4. 稳定性：不稳定

2. 选择排序

2.1.1 选择排序

思想就是便利找到一个最大一个最小最小放在起始位置最大放在最后的位置

代码实现：

void SelectSort(int* a, int n)
{int begin = 0;int end = n - 1;while (begin < end){int maxindex = begin;int minindex = begin;for (int i = begin + 1; i <= end; i++){if (a[i] > a[maxindex]){maxindex = i;}if (a[i] < a[minindex]){minindex = i;}}Swap(&a[begin], &a[minindex]);//这里我们要注意如果maxindex指向与begin相等时，换位之后maxindex要更新if (begin == maxindex)maxindex = minindex;Swap(&a[end], &a[maxindex]);begin++;end--;}
}

2.1.2 选择排序特性

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用

2. 时间复杂度： O(N^2)

3. 空间复杂度： O(1)

4. 稳定性：不稳定

2.2.1 堆排序

堆排序就是先建堆然后按照堆的删除把堆顶数据放到数组最后让后end减减向下调整就行

代码实现如下：

void AddjustDown(int* a, int n, int parent)
{int child = 2 * parent + 1;while (child < n){if (child + 1 < n && a[child + 1] > a[child]){child++;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = 2 * parent + 1;}else{break;}}}
//堆排序
void HeapSort(int* a, int n)
{for (int i = (n - 2) / 2; i >= 0; i--){AddjustDown(a, n, i);}int end = n - 1;while (end >= 0){Swap(&a[0], &a[end]);AddjustDown(a, end, 0);end--;}
}

2.2.2 堆排序特性

1. 堆排序使用堆来选数，效率就高了很多。

2. 时间复杂度： O(N*logN)

3. 空间复杂度： O(1)

4. 稳定性：不稳定

3. 交换排序

3.1.1 冒泡排序

代码实现：

void BubbleSort(int* a, int n)
{for (int i = 0; i < n - 1; i++){int falg = 1;for (int j = 0; j < n - 1 - i ;j++){if (a[j] > a[j + 1]){Swap(&a[j], &a[j + 1]);}falg = 0;}if (falg == 1){break;}}
}

3.1.2 冒泡排序的特性

1. 冒泡排序是一种非常容易理解的排序

2. 时间复杂度： O(N^2)

3. 空间复杂度： O(1)

4. 稳定性：稳定

3.2.1 快速排序

3.2.1.1 hoare版本

这里我们写的是单趟的逻辑

int PartSort1(int* a, int left, int right)
{int keyi = left;int begin = left;int end = right;while (begin < end){while (begin < end && a[end] >= a[keyi]){end--;}while (begin < end && a[begin] <= a[keyi]){begin++;}Swap(&a[end], &a[begin]);}Swap(&a[begin], &a[keyi]);return begin;
}

3.2.1.2 挖坑法

// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{int key = a[left];int keyi = left;int begin = left;int end = right;while (begin < end){while (begin < end && a[end] >= a[keyi]){end--;}a[keyi] = a[end];keyi = end;while (begin < end && a[begin] <= a[keyi]){begin++;}a[keyi] = a[begin];keyi = begin;}a[keyi] = key;return keyi;
}

3.2.1.3 前后指针法

// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{int key = a[left];int prev = left;int cur = prev + 1;while (cur <= right){//这里当我们每次交换时prev先走是为了防止数组最左端的数据被覆盖if (a[cur] < key && ++prev!=cur)Swap(&a[cur], &a[prev]);cur++;}//这里注意要与数组的头一个序列的值交换Swap(&a[prev], &a[left]);	return prev;
}

3.2.2.1 快排的递归实现及优化

// 三数取中
int findmidi(int* a, int left, int right)
{int midi = (right - left) / 2 + left;if (a[left] >= a[midi]){if (a[midi] >=a[right]){return midi;}else if (a[right] >= a[midi]){if (a[left] <= a[right]){return left;}else{return right;}}}else//a[midi]>a[left]{if (a[right] >= a[midi]){return midi;}else if (a[right] <= a[midi]){if (a[right] >= a[left]){return right;}else{return left;}}}
}
void QuickSort(int* a, int left, int right)
{if (left >= right)return ;if (right - left + 1 <= 10){InsertSort(a + left, right - left + 1);return ;}else{int midi = findmidi(a, left, right);Swap(&a[midi], &a[left]);int mid = PartSort3(a, left, right);QuickSort(a, left, mid - 1);QuickSort(a, mid + 1, right);}
}

其中的三数其中发是为了防止数据有序的情况下效率退化

而在数据足够少时不用再递归了减少了递归次数优化了效率

3.2.2.2 快排的非递归实现

 //快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{Stack stack;StackInit(&stack);StackPush(&stack, right);StackPush(&stack, left);while (!StackEmpty(&stack)){int begin = StackTop(&stack);StackPop(&stack);int end = StackTop(&stack);StackPop(&stack);int mid = PartSort3(a, begin, end);if (mid + 1 < end){StackPush(&stack, end);StackPush(&stack, mid + 1);}if (begin < mid - 1){StackPush(&stack, mid - 1);StackPush(&stack, begin);}}StackDestroy(&stack);
}

就是利用栈来存每次递归的区间用栈模拟实现递归过程注意的是每次入栈应该是右区间先入再左区间

3.2.2 快速排序的特性

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫 快速 排序

2. 时间复杂度： O(N*logN)

4. 归并排序

归并排序（ MERGE-SORT ）是建立在归并操作上的一种有效的排序算法 , 该算法是采用分治法（ Divide and

Conquer ）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有

序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：

如果说快排是二叉树的前序则归并就是后序

4.1 归并递归实现

void _MergeSort(int *a, int *tem, int left, int right)
{if (left >= right){return;}int mid = (right - left) / 2 + left;_MergeSort(a, tem, left, mid);_MergeSort(a, tem, mid+1, right);//下面要进行归并排序int j = left;int begin1 = left;int end1 = mid;int begin2 = mid + 1;int  end2 = right;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tem[j++] = a[begin1++];}else{tem[j++] = a[begin2++];}}while (begin1 <= end1){tem[j++] = a[begin1++];}while (begin2 <= end2){tem[j++] = a[begin2++];}memcpy(a + left, tem + left, sizeof(int) * (right - left + 1));
}
//归并排序
void MergeSort(int* a, int n)
{int* tem = (int*)malloc(sizeof(int) * n);int left = 0;int right = n - 1;_MergeSort(a, tem, left, right);
}

注意分区间为什么是以上的分法请看下图

如果[2,3]按照第一种则会一直递归造成栈溢出。

4.2 归并非递归实现

//归并排序非递归写法
void MergeSortNonR(int *a, int n)
{int* tem = (int*)malloc(sizeof(int) * n);if (tem == NULL){perror("malloc faliue");return;}int gap = 1;while (gap <= n){//gap是每组归并数据的数据个数for (int i = 0; i < n; i += 2 * gap){int begin1 = i;int end1 = i + gap - 1;int begin2 = i + gap;int end2 = i + 2 * gap - 1;//第二组全都越界if (begin2 >= n){break;}//第二组部分越界end2更新if (end2 >= n)end2 = n - 1;int j = begin1;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tem[j++] = a[begin1++];}else{tem[j++] = a[begin2++];}}while (begin1 <= end1){tem[j++] = a[begin1++];}while (begin2 <= end2){tem[j++] = a[begin2++];}memcpy(a + i, tem + i, sizeof(int) * (end2 - i + 1));}gap *= 2;}free(tem);tem == NULL;
}

这里我们注意的就是越界问题如果begin2越界说明此次归并不需要了end2越界说明第二组有部分数据需要归并end2更新。如果end1越界此时begin2一定越界直接退出for循环不用进行归并了

5. 非比较排序

5.1 计数排序

代码实现：其实就是一个简单的哈希映射

// 计数排序
void CountSort(int* a, int n)
{//申请一个计数数组int max = a[0];int min = a[0];for (int i = 0; i < n; i++){if (a[i] > max){max = a[i];}if (a[i] < min){min = a[i];}}int range = max - min + 1;int* count = (int*)calloc(range, sizeof(int));for (int i = 0; i < n; i++){count[(a[i]-min)]++;}int j = 0;for (int i = 0; i < range; i++){while (count[i]--){a[j++] = i + min;}}free(count);count = NULL;
}

1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。

2. 时间复杂度： O(MAX(N, 范围 ))

3. 空间复杂度： O( 范围 )

5.2 基数排序

思想就是先按照最低位按照顺序先排接着一直到最高位这里我们只需要了解一下思想就行

5.3 桶排序

思想就是我们建立一个指针数组此时数组里面的元素是一个指向链表结点的指针。

我们便利原数组把最高位对应的数放到指针数组对应的下标比如78，就要放到B数组下标为7的那个数组元素里面如果再来一个76就进行尾插最后对链表排序。

6. 排序算法复杂度及稳定性

稳定性是指两个相同的数在排序前后的相对位置如果不变就是稳定反之则不稳定。

冒泡这里我们这里我们不分析了

选择排序假设6，6，2我们把6和2交换6的相对位置改变了就不稳定了

插入排序是稳定

希尔如果两个相同的数被分到不同的组就会不稳定

堆排如果都是2把2放到最后相对位置改变不稳定

归并排序就是我们在归并时如果相等我们就把左区间的那个值先放到数组中就稳定了

快速排序假设6，6，5我们把6和5交换就会不稳定了