排序: 所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。 稳定性: 若经过排序,这些记录的序列的相对次序保持不变,即在原序列中,r[i] = r[j] ,且 r[i] 在 r[j] 之前,而在排序后的序列中,r[i] 仍在 r[j] 之前,则称这种排序算法是稳定的;否则称为不稳定的。 内部排序: 数据元素全部放在内存中的排序。 外部排序: 数据元素太多不能同时放在内存中,根据排序过程的要求在内存外面的排序。(例如归并排序)
排序 OJ(可使用各种排序跑这个OJ) : 排序数组
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>
void print(int arr[], int n);
// 插入排序
void InsertSort(int arr[], int n);
// 希尔排序
void ShellSort(int arr[], int n);
// 选择排序
void SelectSort(int arr[], int n);
// 堆排序
void AdjustDown(int arr[], int n, int root);
void HeapSort(int arr[], int n);
// 冒泡排序
void BubbleSort(int* a, int n);
// 快速排序递归实现
//三数取中函数
int GetMidIndex(int* a, int left, int right);
void QuickSort(int* a, int left, int right);
// 快速排序hoare版本
int PartSort1(int* a, int left, int right);
// 快速排序挖坑法
int PartSort2(int* a, int left, int right);
// 快速排序前后指针法
int PartSort3(int* a, int left, int right);
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right);
// 归并排序递归实现
void MergeSort(int* a, int n);
// 归并排序非递归实现
void MergeSortNonR(int* a, int n);
// 计数排序
void CountSort(int* a, int n);
#include "sort.h"
// 测试排序的性能对比
void TestOP()
{
srand((unsigned int)time(0));
const int N = 100000;
int* a1 = (int*)malloc(sizeof(int) * N);
int* a2 = (int*)malloc(sizeof(int) * N);
int* a3 = (int*)malloc(sizeof(int) * N);
int* a4 = (int*)malloc(sizeof(int) * N);
int* a5 = (int*)malloc(sizeof(int) * N);
int* a6 = (int*)malloc(sizeof(int) * N);
for (int i = 0; i < N; ++i)
{
a1[i] = rand();
a2[i] = a1[i];
a3[i] = a1[i];
a4[i] = a1[i];
a5[i] = a1[i];
a6[i] = a1[i];
}
int begin1 = clock();
InsertSort(a1, N);
int end1 = clock();
int begin2 = clock();
ShellSort(a2, N);
int end2 = clock();
int begin3 = clock();
SelectSort(a3, N);
int end3 = clock();
int begin4 = clock();
HeapSort(a4, N);
int end4 = clock();
int begin5 = clock();
QuickSort(a5, 0, N - 1);
int end5 = clock();
int begin6 = clock();
MergeSort(a6, N);
int end6 = clock();
printf("InsertSort:%d\n", end1 - begin1);
printf("ShellSort:%d\n", end2 - begin2);
printf("SelectSort:%d\n", end3 - begin3);
printf("HeapSort:%d\n", end4 - begin4);
printf("QuickSort:%d\n", end5 - begin5);
printf("MergeSort:%d\n", end6 - begin6);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
}
void Swap(int* a, int* b)
{
if(*a == *b)//这个条件要加,因为如果两个数相等,会变成0
return;
*a ^= *b;
*b ^= *a;
*a ^= *b;
}
优点: 无需开辟临时变量,且不会发生溢出。
基本思想: 直接插入排序是一种简单的插入排序法,其基本思想是:把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 。 实际中我们玩扑克牌时,就用了插入排序的思想。 直接插入排序: 当插入第 i (i >= 1)个元素时,前面的 array[0], array[1],…,array[i - 1] 已经排好序,此时用 array[i] 的排序码与 array[i - 1],array[i - 2],…的排序码顺序进行比较,找到插入位置即将 array[i] 插入,原来位置上的元素顺序后移。 直接插入排序的特性总结:
代码实现:
void InsertSort(int* arr, int n)
{
for(int i = 0; i < n - 1; ++i)
{
int end = i;
int tmp = arr[end + 1];
while(end >= 0)
{
if(arr[end] > tmp)
{
arr[end + 1] = arr[end];
--end;
}
else
break;
}
arr[end + 1] = tmp;
}
}
希尔排序的由来: 希尔排序是基于插入排序的以下两点性质而提出改进方法的:
在以前排序算法不多的时候,科学家们想着如何优化时间复杂度… 这时希尔想到,插入排序最坏的情况是 O(N^2) ,是在序列逆序的情况下,以目标排升序为例,最大的数字在最前面,那么要是将插入进行分组会不会交换的更快?答案是确实是快了! 因为将插入排序的思想进行分组插入后,如果分组越大,那么大的数字能更快的向后移动,而分组越小,大的数字就会越慢的向后移动。相反,分组越大,那么这个序列也越不接近有序,而分组越小,反而越接近有序。 所以希尔就根据这种特点,创造了缩小增量排序的基本思想! 简单来说: 希尔排序是按照不同步长对元素进行插入排序,==当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小,插入排序对于有序的序列效率很高。==所以,希尔排序的时间复杂度会比o(n^2)好一些。 实质就是一种分组插入的思想! 希尔排序的特性总结:
总结:
gap 越大,大的和小的数可以更快的挪到对应的方向去 gap 越大,越不接近有序
gap 越小,大的和小的数可以更慢的挪到对应的方向去 gap 越小,就越接近有序
代码:
void ShellSort(int* arr, int n)
{
int gap = n;
while(gap > 1)
{
gap = (gap / 3) + 1; //加一防止gap最后为0
for(int i = 0; i < n - gap; ++i)
{
int end = i;
int tmp = arr[end + gap];
while(end >= 0)
{
if(arr[end] > tmp)
{
arr[end + gap] = arr[end];
end -= gap;
}
else
break;
}
arr[end + gap] = tmp;
}
}
}
基本思想:(采用双向选择,同时找大找小,进行一定程度的优化) 每一次从待排序的数据元素中选出最小和最大的两个元素,存放在序列的起始位置以及末尾,直到全部待排序的数据元素排完 。 直接选择排序:
直接选择排序的特性总结:
代码:
void SelectSort(int* arr, int n)
{
int left = 0;
int right = n - 1;
//同时找最大和最小,从两边开始互换位置
while(left <= right)
{
int max = left;
int min = right;
for(int i = left; i < right + 1; ++i)
{
if(arr[i] < min)
min = i
if(arr[i] > max)
max = i;
}
Swap(&arr[left], &arr[right]);
// 如果max和left位置重叠,max被换走了,要修正一下max的位置
if (left == max)
max = min;
Swap(&arr[right], &arr[max]);
left++;
right--;
}
}
堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆,排降序建小堆。 (具体的参考二叉树中的堆的笔记) 堆排序的特性总结:
代码:
//向下调整算法(大堆)
void AdjustDown(int* arr, int n, int root)
{
int parent = root;
int child = parent * 2 + 1;
while(child < n)
{
if (child + 1 < n && arr[child] < arr[child + 1])
{
child += 1;
}
if (arr[parent] < arr[child])
{
Swap(&arr[parent], &arr[child]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
void HeapSort(int* arr, int n)
{
//建大堆
for(int i = (n-1-1) / 2; i >= 0; ++i)
AdjustDown(arr, n, i);
int end = n - 1;
while(end > 0)
{
Swap(&arr[0], &arr[end]);
AdjustDown(arr, end, 0);
--end;
}
}
冒泡排序的特性总结:
代码:
void BubbleSort(int* arr, int n)
{
for(int i = 0; i < n - 1; ++i)
{
int flag = 1;
for(int j = 0; j < n - 1 - i; ++j)
{
if(arr[j] > arr[j + 1])
{
Swap(&arr[j], &arr[j + 1]);
flag = 0;
}
}
if(flag == 1)
break;
}
}
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。 将区间按照基准值划分为左右两半部分的常见方式有:(会一种即可)
快速排序的特性总结:
在写出个版本之前,我们先写出快速排序的主函数,让各版本的快排作为子函数,减少耦合性。
void QuickSort(int* arr, int left, int right)
{
if(left >= right) //递归结束的条件
return;
int key = PartQuickSort(arr, left, right); //将快排作为子函数排序
QuickSort(arr, left, key -1); //继续递归调用子区间
QuickSort(arr, key + 1, right);
}
而在快排的主函数中,我们又可以有以下两种优化手段:
优化的产生原因: 在理想情况下,我们都希望每次更好都是二分,每行有 N 个数,共有 logN 行,所以时间复杂度为O(N*logN) 但是对于最坏的情况,就是这个数据序列本来就有序,共有 N 行,每行分别为 N、N-1、N-2、…、2、1 个,共 N(N-1)/2个。 若进行快排,则会有时间复杂度O(N^2),效率非常低,但是我们可以发现,其实本来就不需要排多少个,居然会花了这么久的时间,所以就有了三数取中的方法,避免了这种最坏的情况。
三数取中:
将每次所给的区间中的 最左边的值 、最右边的值、 最中间的值 ,挑大小为中间的那个,并将这个数与最左边的数交换位置。(因为后面三个版本的排序都以最左边的值为key)。
代码:
int GetMidIndex(int* arr, int left, int right)
{
int mid = (left + right) >> 1; //运用位运算符防止溢出
if (a[left] < a[mid])
{
if (a[mid] < a[right])
return mid;
else if (a[right] < a[left])
return left;
else
return right;
}
else //a[left] >= a[mid]
{
if (a[right] < a[mid])
return mid;
else if (a[left] < a[right])
return left;
else
return right;
}
小区间优化: 当要排的数据序列较大的时候,递归的层数就越深,特别是最后那几层或者几十层。但是我们仔细一想,其实在快排的前面的递归中,大部分区间的数据已经是解决有序了,所以这个时候我们**可以考虑让剩下的几层或者几十层使用插入排序,进行优化,减少递归的深度,防止过多的开辟栈空间。**(效率其实是相差不大的,如今编译器对递归的优化很大,不亚于迭代)
所以将上述的两种优化放到快排的主函数中,代码如下:
void QuickSort(int* a, int left, int right)
{
//记得递归返回条件
if (left >= right)
return;
//分小区间,数据多的继续递归,少的就直接插入排序
//这里的小区间取不同的大小,效果不一样,得看要排的数据多大
if (right - left > 20)
{
//三数取中
int mid = GetMidIndex(a, left, right);
Swap(&a[mid], &a[left]);
int key = PartSort1(a, left, right);
QuickSort(a, left, key - 1);
QuickSort(a, key + 1, right);
}
else
{
InsertSort(a + left, right - left + 1);
}
}
hoare版本比较经典,就是 左右指针法 的思路。 步骤:
代码:
int hoareQuickSort(int* arr, int left, int right)
{
int key = left;
while(left < right)
{
//记得判断left < right,以及要a[right]要>=a[key],否则死循环
while(left < right && arr[right] >= arr[key])
right--;
while(left < right && arr[left] <= arr[key])
left++;
Swap(&arr[left], &arr[right]);
}
//因为是右边先动,所以相遇时候left一定小于key的值,所以无需判断
Swap(&arr[key], &arr[left]);
return left;
}
挖坑法顾名思义就是不断挖坑😄 步骤:
代码:
int holeQuickSort(int* arr, int left, int right)
{
int hole = arr[left];
while(left < right)
{
//找大的
while (left < right && a[right] >= hole)
right--;
//填左边的坑,右边形成了新坑
a[left] = a[right];
//找小的
while (left < right && a[left] <= hole)
left++;
//填右边的坑,左边形成了新坑
a[right] = a[left];
}
//最后用hole把坑填住
a[left] = hole;
return left;
}
步骤:
代码:
int back-and-forthQuickSort(int* arr, int left, int right)
{
int key = left;
int prev = left;
int cur = left + 1;
while(cur <= right)
{
if(arr[cur] < a[key] && prev != cur)
{
prev++;
Swap(&arr[prev], &arr[cur]);
}
cur++;
}
Swap(&arr[key], &arr[prev]);
return prev;
}
思路: 用栈来存储每个子区间的下标。 首先将 left 和 right 入栈,然后进入循环,用 begin 和 end 分别标记每次 出栈的左右区间。接着对该区间进行排序(可以用我们前面实现的三种方式的其中一种),并标注 key ,然后继续将新的 [ begin, key - 1 ] , [ key + 1, end ] 入栈。 若区间只有一个元素了则不入栈。 注: 用迭代主要是为了解决 递归栈溢出 的问题,而不是速度问题,因为现在的编译器优化已经做的很好了。
代码:
#include "stack.h"
void QuickNonSort(int* arr, int left, int right)
{
//三数取中
int mid = GetMidIndex(a, left, right);
Swap(&a[mid], &a[left]);
Stack st; //初始化队列,顺便将left和right放进去
StackInit(&st);
StackPush(&st, left);
StackPush(&st, right);
while(!StackEmpty(&st))
{
int end = StackTop(&st);
StackPop(&st);
int begin = StackTop(&st);
StackPop(&st);
int key = holeQuickSort(arr, begin, end);
if(begin < key - 1)
{
StackPush(&st, begin);
StackPush(&st, key - 1);
}
if(key + 1 < end)
{
StackPush(&st, key + 1);
StackPush(&st, end);
}
}
StackDestroy(&st);
}
基本思想: **归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)**的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。 归并排序核心步骤: 归并排序的特性总结:
思路: 分解与合并过程类似二叉树的后序遍历,假设左区间有序了,右区间也有序了,那么一归并,整个数组就有序了。
代码:
void Merge(int* a, int begin1, int end1, int begin2, int end2, int* tmp)
{
//两端有序子区间归并tmp,并拷贝回去
int j = begin1;
int i = begin1;
while ((begin1 <= end1) && (begin2 <= end2))
{
if (a[begin1] <= a[begin2])
tmp[i++] = a[begin1++];
else
tmp[i++] = a[begin2++];
}
//将有可能还没结束的数据放到tmp中去
while (begin1 <= end1)
tmp[i++] = a[begin1++];
while (begin2 <= end2)
tmp[i++] = a[begin2++];
//拷贝回去
for (j; j <= end2; j++)
a[j] = tmp[j];
}
void _MergeSort(int a[], int left, int right, int* tmp)
{
//递归结束条件
if (left >= right)
return;
//分治步骤:分为[left, mid]和[mid + 1, right]
int mid = (left + right) >> 1;
_MergeSort(a, left, mid, tmp);
_MergeSort(a, mid + 1, right, tmp);
//由于下面迭代(非递归)版本也要用到这部分,所以整合出来当作子函数
Merge(a, left, mid, mid + 1, right, tmp);
}
void MergeSort(int* a, int n) //归并排序的主函数接口
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
printf("malloc fail\n");
exit(-1);
}
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
}
思路: 与递归不同的是,迭代是不需要分解的。**只需要控制好每次归并的区间,让它们从一一归并、二二归并、四四归并…**直到最后归并成一个完整的数组。 注意要点: 归并时候可能存在的三种情况:(1、2点可合成为一点处理)
代码:
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
printf("malloc fail\n");
exit(-1);
}
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n; i += gap * 2)
{
//对区间[i, i+gap-1] [i+gap, i+2*gap-1]归并
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
//归并最后一小组时,如果不存在第二个小区间,则无需归并
if (begin2 >= n)
break;
//归并最后一小组时,如果第二个小区间不够gap个,则要调整一下end2
if (end2 >= n)
end2 = n - 1;
Merge(a, begin1, end1, begin2, end2, tmp); //这个子函数在递归版本中
}
gap *= 2;
}
free(tmp);
}
思想:计数排序又称为鸽巢原理,是对哈希直接定址法的变形应用。 操作步骤:
计数排序的特性总结:
**思考:**若最小的数是从一万开始的,那前面的空间都浪费了,咋办?
方法: 先求出原数组的 **max 和 min **,然后开辟的数组只需要开辟 max - min + 1 个空间就行。 但在计数时候要记得 减去 min,在回收的时候记得 加上 min。
代码:
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*)malloc(sizeof(int) * range);
if (count == NULL)
{
printf("malloc fail\n");
exit(-1);
}
memset(count, 0, sizeof(int) * range);//记得初始化为0
for (int i = 0; i < n; i++)
{
count[a[i] - min] += 1;
}
int j = 0;
for (int i = 0; i < range; i++)
{
while (count[i]--)
{
a[j++] = i + min;
}
}
free(count);
}