精华内容
下载资源
问答
  • 七种常见的数组排序算法整理(C语言版本)
    2021-05-21 15:02:00

    ~~~C语言版本~~~

    冒泡排序

    选择排序

    直接插入排序

    二分插入排序

    希尔排序

    快速排序

    堆排序

    #define EXCHANGE(num1, num2) { num1 = num1 ^ num2;\

    num2 = num1 ^ num2;\

    num1 = num1 ^ num2;}

    排序算法是否稳定:相同元素的相对在排序前后是否会发生改变,如果会,就是不稳定的,否则就是稳定的。

    一.冒泡排序

    冒泡排序原理很容易理解,就是重复地走访过要排序的元素列,依次比较两个相邻的元素,顺序不对就交换,直至没有相邻元素需要交换,也就是排序完成。

    这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。

    冒泡排序是一种稳定排序算法。

    时间复杂度:最好情况(初始情况就是正序)下是o(n),平均情况是o(n²)

    void buddleSort(int num[],int count)

    {

    for (int i = 0; i < count - 1; i++) {

    for (int j = 0; j < count - i - 1; j++) {

    if (num[j] > num[j + 1]) EXCHANGE(num[j], num[j + 1])

    }

    }

    }

    二、选择排序

    选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到全部待排序的数据元素排完。

    选择排序的交换操作介于 0 和 (n - 1) 次之间。选择排序的比较操作为 n (n - 1) / 2 次之间。选择排序的赋值操作介于 0 和 3 (n - 1) 次之间。

    比较次数O(n²),比较次数与关键字的初始状态无关,总的比较次数N=(n-1)+(n-2)+...+1=n*(n-1)/2。交换次数O(n),最好情况是,已经有序,交换0次;最坏情况交换n-1次,逆序交换n/2次。交换次数比冒泡排序少多了,由于交换所需CPU时间比比较所需的CPU时间多,n值较小时,选择排序比冒泡排序快

    选择排序是不稳定的排序方法。

    时间复杂度:最好和平均情况下都是O(n²)

    void selectSort(int num[],int count)

    {

    for (int i = 0; i < count; i++) {

    int min = i;

    for (int j = i; j < count; j++) {

    if (num[j] < num[min]) min = j;

    }

    if (i != min) EXCHANGE(num[i], num[min]);//可以看出,最多交换count - 1次

    }

    }

    三、直接插入排序

    插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,

    插入排序的基本思想是:每步将一个待排序的记录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止

    直接插入排序是稳定的排序算法。

    时间复杂度:最好情况(初始情况就是正序)下是o(n),平均情况是o(n²)

    void insertSort2(int num[],int count)

    {

    int i,j;

    for (i = 1; i < count; i++) {

    if (num[i] < num[i - 1]) {

    int temp = num[i];

    for (j = i; j > 0; j--) {

    if (num[j - 1] > temp) num[j] = num[j - 1];

    else break;

    }

    num[j] = temp;

    }

    }

    }

    四、二分插入排序

    由于在插入排序过程中,待插入数据左边的序列总是有序的,针对有序序列,就可以用二分法去插入数据了,也就是二分插入排序法。适用于数据量比较大的情况。

    二分插入排序的算法思想:

    算法的基本过程:

    (1)计算 0 ~ i-1 的中间点,用 i 索引处的元素与中间值进行比较,如果 i 索引处的元素大,说明要插入的这个元素应该在中间值和刚加入i索引之间,反之,就是在刚开始的位置 到中间值的位置,这样很简单的完成了折半;

    (2)在相应的半个范围里面找插入的位置时,不断的用(1)步骤缩小范围,不停的折半,范围依次缩小为 1/2 1/4 1/8 .......快速的确定出第 i 个元素要插在什么地方;

    (3)确定位置之后,将整个序列后移,并将元素插入到相应位置。

    二分插入排序是稳定的排序算法。

    时间复杂度:最好情况(刚好插入位置为二分位置)下是O(log₂n),平均情况和最坏情况是o(n²)

    void insertSortBinary(int num[],int count)

    {

    int i,j;

    for (i = 1; i < count; i++) {

    if (num[i] < num[i - 1]) {

    int temp = num[i];

    int left = 0,right = i - 1;

    while (left <= right) {

    int mid = (left + right)/2;

    if (num[mid] < temp) left = mid + 1;

    else right = mid - 1;

    }

    //只是比较次数变少了,交换次数还是一样的

    for (j = i; j > left; j--) {

    num[j] = num[j - 1];

    }

    num[left] = temp;

    }

    }

    }

    五、希尔(插入)排序

    希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。

    希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,排序完成。

    希尔排序是非稳定排序算法。

    时间复杂度:O(n^(1.3—2))

    void shellSort(int num[],int count)

    {

    int shellNum = 2;

    int gap = round(count/shellNum);

    while (gap > 0) {

    for (int i = gap; i < count; i++) {

    int temp = num[i];

    int j = i;

    while (j >= gap && num[j - gap] > temp) {

    num[j] = num[j - gap];

    j = j - gap;

    }

    num[j] = temp;

    }

    gap = round(gap/shellNum);

    }

    }

    六、快速排序

    快速排序(Quicksort)是对冒泡排序的一种改进。

    它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

    快速排序是非稳定的排序算法

    时间复杂度:最差为O(n^2),平均为O(nlogn),最好为O(nlogn)

    void quickSort(int num[],int count,int left,int right)

    {

    if (left >= right){

    return ;

    }

    int key = num[left];

    int lp = left; //左指针

    int rp = right; //右指针

    while (lp < rp) {

    if (num[rp] < key) {

    int temp = num[rp];

    for (int i = rp - 1; i >= lp; i--) {

    num[i + 1] = num[i];

    }

    num[lp] = temp;

    lp ++;

    rp ++;

    }

    rp --;

    }

    quickSort(num,count,left,lp - 1);

    quickSort(num,count,rp + 1,right);

    }

    七、堆排序

    是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点

    在堆的数据结构中,堆中的最大值总是位于根节点(在优先队列中使用堆的话堆中的最小值位于根节点)。堆中定义以下几种操作:

    最大堆调整(Max Heapify):将堆的末端子节点作调整,使得子节点永远小于父节点

    创建最大堆(Build Max Heap):将堆中的所有数据重新排序

    堆排序(HeapSort):移除位在第一个数据的根节点,并做最大堆调整的递归运算

    堆排序是一个非稳定的排序算法。

    时间复杂度:O(nlogn)

    void maxHeapify(int num[], int start, int end) {

    //建立父节点指标和子节点指标

    int dad = start;

    int son = dad * 2 + 1;

    while (son <= end) { //若子节点指标在范围内才做比较

    if (son + 1 <= end && num[son] < num[son + 1]) //先比较两个子节点大小,选择最大的

    son++;

    if (num[dad] > num[son]) //如果父节点大於子节点代表调整完毕,直接跳出函数

    return;

    else { //否则交换父子内容再继续子节点和孙节点比较

    EXCHANGE(num[dad], num[son])

    dad = son;

    son = dad * 2 + 1;

    }

    }

    }

    void heapSort(int num[], int count) {

    int i;

    //初始化,i从最後一个父节点开始调整

    for (i = count / 2 - 1; i >= 0; i--)

    maxHeapify(num, i, count - 1);

    //先将第一个元素和已排好元素前一位做交换,再重新调整,直到排序完毕

    for (i = count - 1; i > 0; i--) {

    EXCHANGE(num[0], num[i])

    maxHeapify(num, 0, i - 1);

    }

    }

    更多相关内容
  • 插入排序算法C语言程序,算法思路:先对数组前两个数进行大小比较,将第三个数与前两个数比较,插入合适位置,再将第四个数与前三个数比较并插入,以此类推
  • 合并排序算法C语言源程序,合并排序算法就是将多个有序数据表合并成一个有序数据表,进行两两合并和数据大小比较,算法程序亲测可用。
  • 1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列 2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置 3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动...
  • 八大排序算法C语言实现)

    万次阅读 多人点赞 2021-05-09 13:50:26
    文章目录插入排序插入排序希尔排序选择排序选择排序排序交换排序冒泡排序快速排序并归排序并归排序 插入排序 插入排序 希尔排序 选择排序 选择排序排序 交换排序 冒泡排序 快速排序 并归排序 并归排序 ...


    本次内容大纲:
    在这里插入图片描述
    注:下列八大排序的代码均以排升序为例。

    直接插入排序

    动图演示:
    在这里插入图片描述
     插入排序,又叫直接插入排序。实际中,我们玩扑克牌的时候,就用了插入排序的思想。
    基本思想:
     在待排序的元素中,假设前n-1个元素已有序,现将第n个元素插入到前面已经排好的序列中,使得前n个元素有序。按照此法对所有元素进行插入,直到整个序列有序。

     但我们并不能确定待排元素中究竟哪一部分是有序的,所以我们一开始只能认为第一个元素是有序的,依次将其后面的元素插入到这个有序序列中来,直到整个序列有序为止。
    在这里插入图片描述
    代码:

    //插入排序
    void InsertSort(int* a, int n)
    {
    	int i = 0;
    	for (i = 0; i < n - 1; i++)
    	{
    		int end = i;//记录有序序列的最后一个元素的下标
    		int tmp = a[end + 1];//待插入的元素
    		while (end >= 0)
    		{
    			if (tmp < a[end])//还需继续比较
    			{
    				a[end + 1] = a[end];
    				end--;
    			}
    			else//找到应插入的位置
    			{
    				break;
    			}
    		}
    		a[end + 1] = tmp;
    		//代码执行到此位置有两种情况:
    		//1.待插入元素找到应插入位置(break跳出循环到此)。
    		//2.待插入元素比当前有序序列中的所有元素都小(while循环结束后到此)。
    	}
    }
    

    时间复杂度: O ( N 2 ) O(N^2) O(N2)  空间复杂度: O ( 1 ) O(1) O(1)

    希尔排序

    动图演示:
    在这里插入图片描述
     希尔排序是按其设计者希尔的名字命名的,该算法由希尔1959年公布。希尔可以说是一个脑洞非常大的人,他对普通插入排序的时间复杂度进行分析,得出了以下结论:
     1.普通插入排序的时间复杂度最坏情况下为O(N2),此时待排序列为逆序,或者说接近逆序。
     2.普通插入排序的时间复杂度最好情况下为O(N),此时待排序列为升序,或者说接近升序。

    于是希尔就想:若是能先将待排序列进行一次预排序,使待排序列接近有序(接近我们想要的顺序),然后再对该序列进行一次直接插入排序。因为此时直接插入排序的时间复杂度为O(N),那么只要控制预排序阶段的时间复杂度不超过O(N2),那么整体的时间复杂度就比直接插入排序的时间复杂度低了。
    在这里插入图片描述
    希尔排序,又称缩小增量法。其基本思想是:
     1.先选定一个小于N的整数gap作为第一增量,然后将所有距离为gap的元素分在同一组,并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量,重复上述操作…
     2.当增量的大小减到1时,就相当于整个序列被分到一组,进行一次直接插入排序,排序完成。

    问题:为什么要让gap由大到小呢?
    answer:gap越大,数据挪动得越快;gap越小,数据挪动得越慢。前期让gap较大,可以让数据更快得移动到自己对应的位置附近,减少挪动次数。

    注:一般情况下,取序列的一半作为增量,然后依次减半,直到增量为1(也可自己设置)。

    举个例子分析一下:
     现在我们用希尔排序对该序列进行排序。
    在这里插入图片描述
     我们用序列长度的一半作为第一次排序时gap的值,此时相隔距离为5的元素被分为一组(共分了5组,每组有2个元素),然后分别对每一组进行直接插入排序。
    在这里插入图片描述
     gap的值折半,此时相隔距离为2的元素被分为一组(共分了2组,每组有5个元素),然后再分别对每一组进行直接插入排序。
    在这里插入图片描述
     gap的值再次减半,此时gap减为1,即整个序列被分为一组,进行一次直接插入排序。
    在这里插入图片描述
     该题中,前两趟就是希尔排序的预排序,最后一趟就是希尔排序的直接插入排序。

    代码:

    //希尔排序
    void ShellSort(int* a, int n)
    {
    	int gap = n;
    	while (gap > 1)
    	{
    		gap = gap / 2;//gap折半
    		int i = 0;
    		//进行一趟排序
    		for (i = 0; i < n - gap; i++)
    		{
    			int end = i;
    			int tmp = a[end + gap];
    			while (end >= 0)
    			{
    				if (tmp < a[end])
    				{
    					a[end + gap] = a[end];
    					end -= gap;
    				}
    				else
    				{
    					break;
    				}
    			}
    			a[end + gap] = tmp;
    		}
    	}
    }
    

    时间复杂度: O ( N l o g N ) O(NlogN) O(NlogN)  空间复杂度: O ( 1 ) O(1) O(1)

    平均时间复杂度: O ( N 1.3 ) O(N^{1.3}) O(N1.3)

    选择排序

    动图演示:
    在这里插入图片描述
     选择排序,即每次从待排序列中选出一个最小值,然后放在序列的起始位置,直到全部待排数据排完即可。

    代码:

    //选择排序(一次选一个数)
    void SelectSort(int* a, int n)
    {
    	int i = 0;
    	for (i = 0; i < n; i++)//i代表参与该趟选择排序的第一个元素的下标
    	{
    		int start = i;
    		int min = start;//记录最小元素的下标
    		while (start < n)
    		{
    			if (a[start] < a[min])
    				min = start;//最小值的下标更新
    			start++;
    		}
    		Swap(&a[i], &a[min]);//最小值与参与该趟选择排序的第一个元素交换位置
    	}
    }
    

    时间复杂度: O ( N 2 ) O(N^2) O(N2)  空间复杂度: O ( 1 ) O(1) O(1)

     实际上,我们可以一趟选出两个值,一个最大值一个最小值,然后将其放在序列开头和末尾,这样可以使选择排序的效率快一倍。

    代码:

    //选择排序(一次选两个数)
    void SelectSort(int* a, int n)
    {
    	int left = 0;//记录参与该趟选择排序的第一个元素的下标
    	int right = n - 1;//记录参与该趟选择排序的最后一个元素的下标
    	while (left < right)
    	{
    		int minIndex = left;//记录最小元素的下标
    		int maxIndex = left;//记录最大元素的下标
    		int i = 0;
    		//找出最大值及最小值的下标
    		for (i = left; i <= right; i++)
    		{
    			if (a[i] < a[minIndex])
    				minIndex = i;
    			if (a[i]>a[maxIndex])
    				maxIndex = i;
    		}
    		//将最大值和最小值放在序列开头和末尾
    		Swap(&a[minIndex], &a[left]);
    		if (left == maxIndex)
    		{
    			maxIndex = minIndex;//防止最大值位于序列开头,被最小值交换
    		}
    		Swap(&a[maxIndex], &a[right]);
    		left++;
    		right--;
    	}
    }
    

    时间复杂度: O ( N 2 ) O(N^2) O(N2)  空间复杂度: O ( 1 ) O(1) O(1)

    堆排序

     要学习堆排序,首先要学习堆的向下调整算法,因为要用堆排序,你首先得建堆,而建堆需要执行多次堆的向下调整算法。

    堆的向下调整算法(使用前提):
     若想将其调整为小堆,那么根结点的左右子树必须都为小堆。
     若想将其调整为大堆,那么根结点的左右子树必须都为大堆。
    在这里插入图片描述
    向下调整算法的基本思想(以建大堆为例):
     1.从根结点处开始,选出左右孩子中值较大的孩子。
     2.让大的孩子与其父亲进行比较。
     若大的孩子比父亲还大,则该孩子与其父亲的位置进行交换。并将原来大的孩子的位置当成父亲继续向下进行调整,直到调整到叶子结点为止。
     若大的孩子比父亲小,则不需处理了,调整完成,整个树已经是大堆了。

    图片示例:
    在这里插入图片描述
    堆的向下调整算法代码:

    //堆的向下调整算法
    void AdjustDown(int* a, int n, int root)
    {
    	int parent = root;
    	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;
    		}
    	}
    }
    

     使用堆的向下调整算法,最坏的情况下(即一直需要交换结点),需要循环的次数为:h - 1次(h为树的高度)。而h = log2(N+1)(N为树的总结点数)。所以堆的向下调整算法的时间复杂度为:O(logN)

     上面说到,使用堆的向下调整算法需要满足其根结点的左右子树均为大堆或是小堆才行,那么如何才能将一个任意树调整为堆呢?
     答案很简单,我们只需要从倒数第一个非叶子结点开始,从后往前,按下标,依次作为根去向下调整即可。
    在这里插入图片描述
    建堆代码:

    	//建堆
    	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    	{
    		AdjustDown(php->a, php->size, i);
    	}
    

    那么建堆的时间复杂度又是多少呢?
     当结点数无穷大时,完全二叉树与其层数相同的满二叉树相比较来说,它们相差的结点数可以忽略不计,所以计算时间复杂度的时候我们可以将完全二叉树看作与其层数相同的满二叉树来进行计算。
    在这里插入图片描述
    我们计算建堆过程中总共交换的次数:
    T ( n ) = 1 × ( h − 1 ) + 2 × ( h − 2 ) + . . . + 2 h − 3 × 2 + 2 h − 2 × 1 T(n) = 1\times(h-1) + 2\times(h-2) + ... + 2^{h-3}\times2 + 2^{h-2}\times1 T(n)=1×(h1)+2×(h2)+...+2h3×2+2h2×1
    两边同时乘2得:
    2 T ( n ) = 2 × ( h − 1 ) + 2 2 × ( h − 2 ) + . . . + 2 h − 2 × 2 + 2 h − 1 × 1 2T(n) = 2\times(h-1) + 2^2\times(h-2) + ... + 2^{h-2}\times2 + 2^{h-1}\times1 2T(n)=2×(h1)+22×(h2)+...+2h2×2+2h1×1
    两式相减得:
    T ( n ) = 1 − h + 2 1 + 2 2 + . . . + 2 h − 2 + 2 h − 1 T(n)=1-h+2^1+2^2+...+2^{h-2}+2^{h-1} T(n)=1h+21+22+...+2h2+2h1
    运用等比数列求和得:
    T ( n ) = 2 h − h − 1 T(n)=2^h-h-1 T(n)=2hh1
    由二叉树的性质,有 N = 2 h − 1 N=2^h-1 N=2h1 h = log ⁡ 2 ( N + 1 ) h=\log_2(N+1) h=log2(N+1),于是
    T ( n ) = N − log ⁡ 2 ( N + 1 ) T(n)=N-\log_2(N+1) T(n)=Nlog2(N+1)
    用大O的渐进表示法:
    T ( n ) = O ( N ) T(n)=O(N) T(n)=O(N)

    总结一下:
     堆的向下调整算法的时间复杂度: T ( n ) = O ( log ⁡ N ) T(n)=O(\log N) T(n)=O(logN)
     建堆的时间复杂度: T ( n ) = O ( N ) T(n)=O(N) T(n)=O(N)

    那么堆建好后,如何进行堆排序呢?
    步骤如下:
     1、将堆顶数据与堆的最后一个数据交换,然后对根位置进行一次堆的向下调整,但是调整时被交换到最后的那个最大的数不参与向下调整。
     2、完成步骤1后,这棵树除最后一个数之外,其余数又成一个大堆,然后又将堆顶数据与堆的最后一个数据交换,这样一来,第二大的数就被放到了倒数第二个位置上,然后该数又不参与堆的向下调整…反复执行下去,直到堆中只有一个数据时便结束。此时该序列就是一个升序。

    堆排序代码:

    //堆排序
    void HeapSort(int* a, int n)
    {
    	//排升序,建大堆
    	//从第一个非叶子结点开始向下调整,一直到根
    	int i = 0;
    	for (i = (n - 1 - 1) / 2; i >= 0; i--)
    	{
    		AdjustDown(a, n, i);
    	}
    	int end = n - 1;//记录堆的最后一个数据的下标
    	while (end)
    	{
    		Swap(&a[0], &a[end]);//将堆顶的数据和堆的最后一个数据交换
    		AdjustDown(a, end, 0);//对根进行一次向下调整
    		end--;//堆的最后一个数据的下标减一
    	}
    }
    

    时间复杂度: O ( N l o g N ) O(NlogN) O(NlogN)  空间复杂度: O ( 1 ) O(1) O(1)

    冒泡排序

    动图演示:
    在这里插入图片描述
    冒泡排序,该排序的命名非常形象,即一个个将气泡冒出。冒泡排序一趟冒出一个最大(或最小)值。
    在这里插入图片描述
    代码:

    //冒泡排序
    void BubbleSort(int* a, int n)
    {
    	int end = 0;
    	for (end = n - 1; end >= 0; end--)
    	{
    		int exchange = 0;//记录该趟冒泡排序是否进行过交换
    		int i = 0;
    		for (i = 0; i < end; i++)
    		{
    			if (a[i]>a[i + 1])
    			{
    				Swap(&a[i], &a[i + 1]);
    				exchange = 1;
    			}
    		}
    		if (exchange == 0)//该趟冒泡排序没有进行过交换,已有序
    			break;
    	}
    }
    

    时间复杂度: O ( N 2 ) O(N^2) O(N2)  空间复杂度: O ( 1 ) O(1) O(1)

    快速排序

    快速排序是公认的排序之王,快速排序是Hoare于1962年提出的一种二叉树结构的交换排序算法,其基本思想为:
     任取待排序元素序列中的某元素作为基准值,按照该基准值将待排序列分为两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后左右序列重复该过程,直到所有元素都排列在相应位置上为止。

    对于如何按照基准值将待排序列分为两子序列,常见的方式有:
     1、Hoare版本
     2、挖坑法
     3、前后指针法

    递归实现

    Hoare版本

    单趟的动图演示:
    在这里插入图片描述
    Hoare版本的单趟排序的基本步骤如下:
     1、选出一个key,一般是最左边或是最右边的。
     2、定义一个L和一个R,L从左向右走,R从右向左走。(需要注意的是:若选择最左边的数据作为key,则需要R先走;若选择最右边的数据作为key,则需要L先走)。
     3、在走的过程中,若R遇到小于key的数,则停下,L开始走,直到L遇到一个大于key的数时,将L和R的内容交换,R再次开始走,如此进行下去,直到L和R最终相遇,此时将相遇点的内容与key交换即可。(选取最左边的值作为key)

     经过一次单趟排序,最终使得key左边的数据全部都小于key,key右边的数据全部都大于key。

     然后我们在将key的左序列和右序列再次进行这种单趟排序,如此反复操作下去,直到左右序列只有一个数据,或是左右序列不存在时,便停止操作,因为这种序列可以认为是有序的。

    代码:

    //快速排序(Hoare版本)
    void QuickSort1(int* a, int begin, int end)
    {
    	if (begin >= end)//当只有一个数据或是序列不存在时,不需要进行操作
    		return;
    		
    	int left = begin;//L
    	int right = end;//R
    	int keyi = left;//key的下标
    	while (left < right)
    	{
    		//right先走,找小
    		while (left < right&&a[right] >= a[keyi])
    		{
    			right--;
    		}
    		//left后走,找大
    		while (left < right&&a[left] <= a[keyi])
    		{
    			left++;
    		}
    		if (left < right)//交换left和right的值
    		{
    			Swap(&a[left], &a[right]);
    		}
    	}
    	int meeti = left;//L和R的相遇点
    	Swap(&a[keyi], &a[meeti]);//交换key和相遇点的值
    
    	QuickSort1(a, begin, meeti - 1);//key的左序列进行此操作
    	QuickSort1(a, meeti + 1, end);//key的右序列进行此操作
    }
    

    时间复杂度: O ( N l o g N ) O(NlogN) O(NlogN)

    挖坑法

    单趟的动图演示:
    在这里插入图片描述
    挖坑法的单趟排序的基本步骤如下:
     1、选出一个数据(一般是最左边或是最右边的)存放在key变量中,在该数据位置形成一个坑。
     2、还是定义一个L和一个R,L从左向右走,R从右向左走。(若在最左边挖坑,则需要R先走;若在最右边挖坑,则需要L先走)。
     3、在走的过程中,若R遇到小于key的数,则将该数抛入坑位,并在此处形成一个坑位,这时L再向后走,若遇到大于key的数,则将其抛入坑位,又形成一个坑位,如此循环下去,直到最终L和R相遇,这时将key抛入坑位即可。(选取最左边的作为坑位)

     经过一次单趟排序,最终也使得key左边的数据全部都小于key,key右边的数据全部都大于key。

     然后也是将key的左序列和右序列再次进行这种单趟排序,如此反复操作下去,直到左右序列只有一个数据,或是左右序列不存在时,便停止操作。

    代码:

    //快速排序(挖坑法)
    void QuickSort2(int* a, int begin, int end)
    {
    	if (begin >= end)//当只有一个数据或是序列不存在时,不需要进行操作
    		return;
    
    	int left = begin;//L
    	int right = end;//R
    	int key = a[left];//在最左边形成一个坑位
    	while (left < right)
    	{
    		//right向左,找小
    		while (left < right&&a[right] >= key)
    		{
    			right--;
    		}
    		//填坑
    		a[left] = a[right];
    		//left向右,找大
    		while (left < right&&a[left] <= key)
    		{
    			left++;
    		}
    		//填坑
    		a[right] = a[left];
    	}
    	int meeti = left;//L和R的相遇点
    	a[meeti] = key;//将key抛入坑位
    
    	QuickSort2(a, begin, meeti - 1);//key的左序列进行此操作
    	QuickSort2(a, meeti + 1, end);//key的右序列进行此操作
    }
    

    时间复杂度: O ( N l o g N ) O(NlogN) O(NlogN)

    前后指针法

    单趟的动图演示:
    在这里插入图片描述
    前后指针法的单趟排序的基本步骤如下:
     1、选出一个key,一般是最左边或是最右边的。
     2、起始时,prev指针指向序列开头,cur指针指向prev+1。
     3、若cur指向的内容小于key,则prev先向后移动一位,然后交换prev和cur指针指向的内容,然后cur指针++;若cur指向的内容大于key,则cur指针直接++。如此进行下去,直到cur指针越界,此时将key和prev指针指向的内容交换即可。

     经过一次单趟排序,最终也能使得key左边的数据全部都小于key,key右边的数据全部都大于key。

     然后也还是将key的左序列和右序列再次进行这种单趟排序,如此反复操作下去,直到左右序列只有一个数据,或是左右序列不存在时,便停止操作。

    代码:

    //快速排序(前后指针法)
    void QuickSort3(int* a, int begin, int end)
    {
    	if (begin >= end)//当只有一个数据或是序列不存在时,不需要进行操作
    		return;
    
    	//三数取中
    	int midIndex = GetMidIndex(a, begin, end);
    	Swap(&a[begin], &a[midIndex]);
    
    	int prev = begin;
    	int cur = begin + 1;
    	int keyi = begin;
    	while (cur <= end)//当cur未越界时继续
    	{
    		if (a[cur] < a[keyi] && ++prev != cur)//cur指向的内容小于key
    		{
    			Swap(&a[prev], &a[cur]);
    		}
    		cur++;
    	}
    	int meeti = prev;//cur越界时,prev的位置
    	Swap(&a[keyi], &a[meeti]);//交换key和prev指针指向的内容
    
    	QuickSort3(a, begin, meeti - 1);//key的左序列进行此操作
    	QuickSort3(a, meeti + 1, end);//key的右序列进行此操作
    }
    

    时间复杂度: O ( N l o g N ) O(NlogN) O(NlogN)

    非递归实现

     当我们需要将一个用递归实现的算法改为非递归时,一般需要借用一个数据结构,那就是栈。将Hoare版本、挖坑法以及前后指针法的快速排序改为非递归版本,其实主体思想一致,只是调用的单趟排序的算法不同而已。
     于是我们可以先将Hoare版本、挖坑法和前后指针法的单趟排序单独封装起来。然后写一个非递归的快速排序,在函数内部调用单趟排序的函数即可。

    Hoare版本

    Hoare版本的单趟排序代码:

    //Hoare版本(单趟排序)
    int PartSort1(int* a, int left, int right)
    {
    	int keyi = left;//key的下标
    	while (left < right)
    	{
    		//right走,找小
    		while (left < right&&a[right] >= a[keyi])
    		{
    			right--;
    		}
    		//left先走,找大
    		while (left < right&&a[left] <= a[keyi])
    		{
    			left++;
    		}
    		if (left < right)
    		{
    			Swap(&a[left], &a[right]);//交换left和right的值
    		}
    	}
    	int meeti = left;//L和R的相遇点
    	Swap(&a[keyi], &a[meeti]);//交换key和相遇点的值
    	return meeti;//返回相遇点,即key的当前位置
    }
    

    挖坑法

    挖坑法的单趟排序代码:

    //挖坑法(单趟排序)
    int PartSort2(int* a, int left, int right)
    {
    	int key = a[left];//在最左边形成一个坑位
    	while (left < right)
    	{
    		//right向左,找小
    		while (left < right&&a[right] >= key)
    		{
    			right--;
    		}
    		//填坑
    		a[left] = a[right];
    		//left向右,找大
    		while (left < right&&a[left] <= key)
    		{
    			left++;
    		}
    		//填坑
    		a[right] = a[left];
    	}
    	int meeti = left;//L和R的相遇点
    	a[meeti] = key;//将key抛入坑位
    	return meeti;//返回key的当前位置
    }
    

    前后指针法

    前后指针法的单趟排序代码:

    //前后指针法(单趟排序)
    int PartSort3(int* a, int left, int right)
    {
    	int prev = left;
    	int cur = left + 1;
    	int keyi = left;
    	while (cur <= right)//当cur未越界时继续
    	{
    		if (a[cur] < a[keyi] && ++prev != cur)//cur指向的内容小于key
    		{
    			Swap(&a[prev], &a[cur]);
    		}
    		cur++;
    	}
    	int meeti = prev;//cur越界时,prev的位置
    	Swap(&a[keyi], &a[meeti]);//交换key和prev指针指向的内容
    	return meeti;//返回key的当前位置
    }
    

    快速排序的非递归算法基本思路:
     1、先将待排序列的第一个元素的下标和最后一个元素的下标入栈。
     2、当栈不为空时,读取栈中的信息(一次读取两个:一个是L,另一个是R),然后调用某一版本的单趟排序,排完后获得了key的下标,然后判断key的左序列和右序列是否还需要排序,若还需要排序,就将相应序列的L和R入栈;若不需排序了(序列只有一个元素或是不存在),就不需要将该序列的信息入栈。
     3、反复执行步骤2,直到栈为空为止。

    代码:

    //快速排序(非递归实现)
    void QuickSortNonR(int* a, int begin, int end)
    {
    	Stack st;//创建栈
    	StackInit(&st);//初始化栈
    	StackPush(&st, begin);//待排序列的L
    	StackPush(&st, end);//待排序列的R
    	while (!StackEmpty(&st))
    	{
    		int right = StackTop(&st);//读取R
    		StackPop(&st);//出栈
    		int left = StackTop(&st);//读取L
    		StackPop(&st);//出栈
    		//该处调用的是Hoare版本的单趟排序
    		int keyi = PartSort1(a, left, right);
    		if (left < keyi - 1)//该序列的左序列还需要排序
    		{
    			StackPush(&st, left);//左序列的L入栈
    			StackPush(&st, keyi - 1);//左序列的R入栈
    		}
    		if (keyi + 1 < right)// 该序列的右序列还需要排序
    		{
    			StackPush(&st, keyi + 1);//右序列的L入栈
    			StackPush(&st, right);//右序列的R入栈
    		}
    	}
    	StackDestroy(&st);//销毁栈
    }
    

    时间复杂度: O ( N l o g N ) O(NlogN) O(NlogN)

    快速排序的两个优化

    三数取中

     快速排序的时间复杂度是O(NlogN),是我们在理想情况下计算的结果。在理想情况下,我们每次进行完单趟排序后,key的左序列与右序列的长度都相同:
    在这里插入图片描述
     若每趟排序所选的key都正好是该序列的中间值,即单趟排序结束后key位于序列正中间,那么快速排序的时间复杂度就是O(NlogN)。

     可是谁能保证你每次选取的key都是正中间的那个数呢?当待排序列本就是一个有序的序列时,我们若是依然每次都选取最左边或是最右边的数作为key,那么快速排序的效率将达到最低:
    在这里插入图片描述
     可以看到,这种情况下,快速排序的时间复杂度退化为O(N2)。其实,对快速排序效率影响最大的就是选取的key,若选取的key越接近中间位置,则则效率越高。

    为了避免这种极端情况的发生,于是出现了三数取中:
     三数取中,当中的三数指的是:最左边的数、最右边的数以及中间位置的数。三数取中就是取这三个数当中,值的大小居中的那个数作为该趟排序的key。这就确保了我们所选取的数不会是序列中的最大或是最小值了。

    代码:

    //三数取中
    int GetMidIndex(int* a, int left, int right)
    {
    	int mid = left + (right - left) / 2;
    	if (a[mid] > a[left])
    	{
    		if (a[mid] < a[right])
    			return mid;
    		else if (a[left]>a[right])
    			return left;
    		else
    			return right;
    	}
    	else
    	{
    		if (a[mid] > a[right])
    			return mid;
    		else if (a[left] > a[right])
    			return right;
    		else
    			return left;
    	}
    }
    

    注意:当大小居中的数不在序列的最左或是最右端时,我们不是就以居中数的位置作为key的位置,而是将key的值与最左端的值进行交换,这样key就还是位于最左端了,所写代码就无需改变,而只需在单趟排序代码开头加上以下两句代码即可:

    	int midIndex = GetMidIndex(a, begin, end);//获取大小居中的数的下标
    	Swap(&a[begin], &a[midIndex]);//将该数与序列最左端的数据交换
    	//以下代码保持不变...
    

    小区间优化

     我们可以看到,就算是上面理想状态下的快速排序,也不能避免随着递归的深入,每一层的递归次数会以2倍的形式快速增长。
     为了减少递归树的最后几层递归,我们可以设置一个判断语句,当序列的长度小于某个数的时候就不再进行快速排序,转而使用其他种类的排序。小区间优化若是使用得当的话,会在一定程度上加快快速排序的效率,而且待排序列的长度越长,该效果越明显。

    代码示例:

    //优化后的快速排序
    void QuickSort0(int* a, int begin, int end)
    {
    	if (begin >= end)//当只有一个数据或是序列不存在时,不需要进行操作
    		return;
    
    	if (end - begin + 1 > 20)//可自行调整
    	{
    		//可调用快速排序的单趟排序三种中的任意一种
    		//int keyi = PartSort1(a, begin, end);
    		//int keyi = PartSort2(a, begin, end);
    		int keyi = PartSort3(a, begin, end);
    		QuickSort(a, begin, keyi - 1);//key的左序列进行此操作
    		QuickSort(a, keyi + 1, end);//key的右序列进行此操作
    	}
    	else
    	{
    		//HeapSort(a, end - begin + 1);
    		ShellSort(a, end - begin + 1);//当序列长度小于等于20时,使用希尔排序
    	}
    }
    

    归并排序

    动图演示:
    在这里插入图片描述
     归并排序是采用分治法的一个非常典型的应用。其基本思想是:将已有序的子序合并,从而得到完全有序的序列,即先使每个子序有序,再使子序列段间有序。

     相信大家都知道如何将两个有序序列合为一个有序序列吧:
    在这里插入图片描述
     那么如何得到有序的子序列呢?当序列分解到只有一个元素或是没有元素时,就可以认为是有序了,这时分解就结束了,开始合并:
    在这里插入图片描述

    递归实现

     归并排序,从其思想上看就很适合使用递归来实现,并且用递归实现也比较简单。其间我们需要申请一个与待排序列大小相同的数组用于合并过程两个有序的子序列,合并完毕后再将数据拷贝回原数组。

    代码:

    //归并排序(子函数)
    void _MergeSort(int* a, int left, int right, int* tmp)
    {
    	if (left >= right)//归并结束条件:当只有一个数据或是序列不存在时,不需要再分解
    	{
    		return;
    	}
    	int mid = left + (right - left) / 2;//中间下标
    	_MergeSort(a, left, mid, tmp);//对左序列进行归并
    	_MergeSort(a, mid + 1, right, tmp);//对右序列进行归并
    	int begin1 = left, end1 = mid;
    	int begin2 = mid + 1, end2 = right;
    	//将两段子区间进行归并,归并结果放在tmp中
    	int i = left;
    	while (begin1 <= end1&&begin2 <= end2)
    	{
    		//将较小的数据优先放入tmp
    		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++];
    	//归并完后,拷贝回原数组
    	int j = 0;
    	for (j = left; j <= right; j++)
    		a[j] = tmp[j];
    }
    //归并排序(主体函数)
    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);//释放空间
    }
    

    时间复杂度: O ( N l o g N ) O(NlogN) O(NlogN)  空间复杂度: O ( N ) O(N) O(N)

    非递归实现

     归并排序的非递归算法并不需要借助栈来完成,我们只需要控制每次参与合并的元素个数即可,最终便能使序列变为有序:
    在这里插入图片描述
     当然,以上例子是一个待排序列长度比较特殊的例子,我们若是想写出一个广泛适用的程序,必定需要考虑到某些极端情况:
    情况一:
     当最后一个小组进行合并时,第二个小区间存在,但是该区间元素个数不够gap个,这时我们需要在合并序列时,对第二个小区间的边界进行控制。
    在这里插入图片描述
    情况二:
     当最后一个小组进行合并时,第二个小区间不存在,此时便不需要对该小组进行合并。
    在这里插入图片描述
    情况三:
     当最后一个小组进行合并时,第二个小区间不存在,并且第一个小区间的元素个数不够gap个,此时也不需要对该小组进行合并。(可与情况二归为一类)
    在这里插入图片描述
     只要把控好这三种特殊情况,写出归并排序的非递归算法便轻而易举了。

    代码:

    //归并排序(子函数)
    void _MergeSortNonR(int* a, int* tmp, int begin1, int end1, int begin2, int end2)
    {
    	int j = begin1;
    	//将两段子区间进行归并,归并结果放在tmp中
    	int i = begin1;
    	while (begin1 <= end1&&begin2 <= end2)
    	{
    		//将较小的数据优先放入tmp
    		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 <= end2; j++)
    		a[j] = tmp[j];
    }
    //归并排序(主体函数)
    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)
    	{
    		int i = 0;
    		for (i = 0; i < n; i += 2 * gap)
    		{
    			int begin1 = i, end1 = i + gap - 1;
    			int begin2 = i + gap, end2 = i + 2 * gap - 1;
    			if (begin2 >= n)//最后一组的第二个小区间不存在或是第一个小区间不够gap个,此时不需要对该小组进行合并
    				break;
    			if (end2 >= n)//最后一组的第二个小区间不够gap个,则第二个小区间的后界变为数组的后界
    				end2 = n - 1;
    			_MergeSortNonR(a, tmp, begin1, end1, begin2, end2);//合并两个有序序列
    		}
    		gap = 2 * gap;//下一趟需合并的子序列中元素的个数翻倍
    	}
    	free(tmp);//释放空间
    }
    

    时间复杂度: O ( N l o g N ) O(NlogN) O(NlogN)  空间复杂度: O ( N ) O(N) O(N)

    外排序

    首先,我先说明一下什么是内排序,什么是外排序:
     内排序:数据量相对少一些,可以放到内存中进行排序。
     外排序:数据量较大,内存中放不下,数据只能放到磁盘文件中,需要排序。

     上面介绍的排序算法均是在内存中进行的,对于数据量庞大的序列,上面介绍的排序算法都束手无策,而归并排序却能胜任这种海量数据的排序。

     假设现在有10亿个整数(4GB)存放在文件A中,需要我们进行排序,而内存一次只能提供512MB空间,归并排序解决该问题的基本思路如下:
     1、每次从文件A中读取八分之一,即512MB到内存中进行排序(内排序),并将排序结果写入到一个文件中,然后再读取八分之一,重复这个过程。那么最终会生成8个各自有序的小文件(A1~A8)。
     2、对生成的8个小文件进行11合并,最终8个文件被合成为4个,然后再11合并,就变成2个文件了,最后再进行一次11合并,就变成1个有序文件了。

    注意:这里将两个文件进行11合并,并不是先将两个文件读入内存然后进行合并,因为内存装不下。这里的11合并是利用文件输入输出函数,从两个文件中各自读取一个数据,然后进行比较,将较小的数据写入到一个新文件中去,然后再读取,再比较,再写入,最终将两个文件中的数据全部写入到另一个文件中去,那么此时这个文件又是一个有序的文件了。
    在这里插入图片描述
    当然,你也可以这样合并文件:
    在这里插入图片描述
    外排序代码示例:

    //将file1文件和file2文件中的数据归并到mfile文件中
    void _MergeFile(const char* file1, const char* file2, const char* mfile)
    {
    	FILE* fout1 = fopen(file1, "r");//打开file1文件
    	if (fout1 == NULL)
    	{
    		printf("打开文件失败\n");
    		exit(-1);
    	}
    
    	FILE* fout2 = fopen(file2, "r");//打开file2文件
    	if (fout2 == NULL)
    	{
    		printf("打开文件失败\n");
    		exit(-1);
    	}
    
    	FILE* fin = fopen(mfile, "w");//打开mfile文件
    	if (fin == NULL)
    	{
    		printf("打开文件失败\n");
    		exit(-1);
    	}
    
    	int num1, num2;
    	int ret1 = fscanf(fout1, "%d\n", &num1);//读取file1文件中的数据
    	int ret2 = fscanf(fout2, "%d\n", &num2);//读取file2文件中的数据
    	while (ret1 != EOF && ret2 != EOF)
    	{
    		//将读取到的较小值写入到mfile文件中,继续从file1和file2中读取数据进行比较
    		if (num1 < num2)
    		{
    			fprintf(fin, "%d\n", num1);
    			ret1 = fscanf(fout1, "%d\n", &num1);
    		}
    		else
    		{
    			fprintf(fin, "%d\n", num2);
    			ret2 = fscanf(fout2, "%d\n", &num2);
    		}
    	}
    	//将file1文件中未读取完的数据写入文件mfile中
    	while (ret1 != EOF)
    	{
    		fprintf(fin, "%d\n", num1);
    		ret1 = fscanf(fout1, "%d\n", &num1);
    	}
    	//将file2文件中未读取完的数据写入文件mfile中
    	while (ret2 != EOF)
    	{
    		fprintf(fin, "%d\n", num2);
    		ret2 = fscanf(fout2, "%d\n", &num2);
    	}
    	fclose(fout1);//关闭file1文件
    	fclose(fout2);//关闭file2文件
    	fclose(fin);//关闭mfile文件
    }
    //将文件中的数据进行排序
    void MergeSortFile(const char* file)
    {
    	FILE* fout = fopen(file, "r");//打开文件
    	if (fout == NULL)
    	{
    		printf("打开文件失败\n");
    		exit(-1);
    	}
    	// 分割成一段一段数据,内存排序后写到小文件中
    	int n = 10;//一次读取10个数据进行内排序
    	int a[10];//读取数据放到数组中,准备进行内排序
    	int i = 0;
    	int num = 0;
    	char subfile[20];//文件名字符串
    	int filei = 1;//储存第filei组内排序后的数据的文件的文件名
    
    	memset(a, 0, sizeof(int)*n);//将数组a的空间置0
    	while (fscanf(fout, "%d\n", &num) != EOF)//从文件中读取数据
    	{
    		if (i < n - 1)//读取前9个数据
    		{
    			a[i++] = num;
    		}
    		else//读取第10个数据
    		{
    			a[i] = num;
    			QuickSort(a, 0, n - 1);//将这10个数据进行快速排序
    			sprintf(subfile, "%d", filei++);//将储存第filei组内排序后的数据的文件的文件名命名为filei
    			FILE* fin = fopen(subfile, "w");//创建一个以字符串subfile[20]为名字的文件并打开
    			if (fin == NULL)
    			{
    				printf("打开文件失败\n");
    				exit(-1);
    			}
    			//将内排序排好的数据写入到subfile文件中
    			for (int i = 0; i < n; i++)
    			{
    				fprintf(fin, "%d\n", a[i]);
    			}
    			fclose(fin);//关闭subfile文件
    
    			i = 0;
    			memset(a, 0, sizeof(int)*n);//将a数组内存置0,准备再次读取10个数据进行内排序
    		}
    	}
    	// 利用互相归并到文件,实现整体有序
    	char mfile[100] = "12";//归并后文件的文件名
    	char file1[100] = "1";//待归并的第一个文件的文件名
    	char file2[100] = "2";//待归并的第二个文件的文件名
    	for (int i = 2; i <= n; ++i)
    	{
    		//将file1文件和file2文件中的数据归并到mfile文件中
    		_MergeFile(file1, file2, mfile);
    
    		strcpy(file1, mfile);//下一次待归并的第一个文件就是上一次归并好的文件
    		sprintf(file2, "%d", i + 1);//上一次待归并的第二个文件的文件名加一,就是下一次待归并的第二个文件的文件名
    		sprintf(mfile, "%s%d", mfile, i + 1);//下一次归并后文件的文件名
    	}
    
    	fclose(fout);//关闭文件
    }
    //主函数
    int main()
    {
    	MergeSortFile("Sort.txt");//将Sort.txt文件中的数据进行排序
    	return 0;
    }
    

    注:代码中使用的是第二种文件合并的方式。

    计数排序

     计数排序,又叫非比较排序。顾名思义,该算法不是通过比较数据的大小来进行排序的,而是通过统计数组中相同元素出现的次数,然后通过统计的结果将序列回收到原来的序列中。

    举个例子:
    在这里插入图片描述
     上列中的映射方法称为绝对映射,即arr数组中的元素是几就在count数组中下标为几的位置++,但这样会造成空间浪费。例如,我们要将数组:1020,1021,1018,进行排序,难道我们要开辟1022个整型空间吗?
     若是使用计数排序,我们应该使用相对映射,简单来说,数组中的最小值就相对于count数组中的0下标,数组中的最大值就相对于count数组中的最后一个下标。这样,对于数组:1020,1021,1018,我们就只需要开辟用于储存4个整型的空间大小了,此时count数组中下标为i的位置记录的实际上是1018+i这个数出现的次数。

    总结:
     绝对映射:count数组中下标为i的位置记录的是arr数组中数字i出现的次数。
     相对映射:count数组中下标为i的位置记录的是arr数组中数字min+i出现的次数。

    注:计数排序只适用于数据范围较集中的序列的排序,若待排序列的数据较分散,则会造成空间浪费,并且计数排序只适用于整型排序,不适用与浮点型排序。

    代码:

    //计数排序
    void CountSort(int* a, int n)
    {
    	int min = a[0];//记录数组中的最小值
    	int max = a[0];//记录数组中的最大值
    	for (int i = 0; i < n; i++)
    	{
    		if (a[i] < min)
    			min = a[i];
    		if (a[i] > max)
    			max = a[i];
    	}
    	int range = max - min + 1;//min和max之间的自然数个数(包括min和max本身)
    	int* count = (int*)calloc(range, sizeof(int));//开辟可储存range个整型的内存空间,并将内存空间置0
    	if (count == NULL)
    	{
    		printf("malloc fail\n");
    		exit(-1);
    	}
    	//统计相同元素出现次数(相对映射)
    	for (int i = 0; i < n; i++)
    	{
    		count[a[i] - min]++;
    	}
    	int i = 0;
    	//根据统计结果将序列回收到原来的序列中
    	for (int j = 0; j < range; j++)
    	{
    		while (count[j]--)
    		{
    			a[i++] = j + min;
    		}
    	}
    	free(count);//释放空间
    }
    

    时间复杂度: O ( N + r a n g e ) O(N+range) O(N+range)  空间复杂度: O ( r a n g e ) O(range) O(range)

    展开全文
  • 冒泡排序法 题目描述:  用一维数组存储学号和... 如果学生的成绩相同,则按照学号的大小进行从小到大排序。 样例输入:  3  1 90  2 87  3 92 样例输出:  2 87  1 90  3 92 代码:   #include <stdio>
  • 排序算法之插入排序C语言

    千次阅读 2020-03-28 16:03:12
    插入排序算法核心思想:将无序数组中的元素,根据其值的大小,插入有序子数组中。类似于我们打扑克牌的时候,一边摸牌,一遍摆牌。遇到小的直接插到牌首,遇到大的直接插入牌尾,遇到中间的则在中间空出一个位置,将...

    一、原理讲解

    插入排序算法核心思想:将无序数组中的元素,根据其值的大小,插入有序子数组中。类似于我们打扑克牌的时候,一边摸牌,一遍摆牌。遇到小的直接插到牌首,遇到大的直接插入牌尾,遇到中间的则在中间空出一个位置,将其插入。

    假定有一个无序数组 arr[10] = {10, 1, 0, 44, 5, 6, 77, 8, 10, 99};

    第一步,直接将无序数组的第一个元素划分到有序子数组当中去,将原来的数组构造成有序子数组和无序子数组两个部分。

    第二步,将无序子数组的第一个元素缓存下来,存到temp变量里面,并且使用temp和有序子数组最后一个元素(arr[0])比较,若temp > arr[0],则直接将temp存到arr[1]当中,若temp < arr[0] 则将arr[0]这个元素后移,存到arr[1]的位置,并且将temp存到arr[0]之中。因为arr[0]前面已经没有数据了。

    第三步,有序子数组已有两个数据,无序子数组只剩8个数组,该轮比较我们将arr[2]存到temp当中,使用temp与arr[1]比较,此时我们发现,temp为0, arr[1] 为10,temp  < arr[1],所以我们需要将arr[1]元素后移,保存到arr[2]的位置上,接着用temp和arr[0]比较,temp < arr[0],因此我们继续将arr[0]后移且存到arr[1]的位置上,最后将temp存到arr[0]的位置上。

    按照这个步骤我们对剩下的数据依次进行比较,并且无需子数组中的数据插入到有序子数组中相应的位置上,直至无序子数组元素为空位置,最终得到结果为:

     

    二、具体代码

    /*
    函数名:int InsertSort(int data[], int n);
    函数功能:使用插入排序的方法,将数组按从小到大排序
    函数参数:
             data[]:数组首地址
             n:参与排序的数据个数
    函数返回值:
               函数成功排序数组返回0,失败返回-1
    */
    
    int InsertSort(int data[], int n)
    {
    	if (NULL == data)
    	{
    		printf("\n data is null \n");
    		return -1;
    	}
    	
    	int i = 0;
    	int j = 0;
    	int temp = 0;
    
    	for (i = 1; i < n; i++)
    	{
    		if (data[i] < data[i - 1])        //程序优化,若无序子数组第一个元素大于有序子数组            
    		{                                 //最后一个元素,直接插入,不进行下面的操作
    			temp = data[i];           
    			j = i - 1;
    			
    			while (j >= 0 && temp < data[j])
    			{
    				data[j + 1] = data[j];
    				j--;
    			}
    			data[j + 1] = temp;      //因为数据比较之后会进行j--
    		}
    	}
    	
    	return 0;
    }

     

    仓促成文,不当之处,尚祈方家和读者批评指正。联系邮箱1772348223@qq.com

     

     

    展开全文
  • 冒泡排序算法C语言版)

    万次阅读 多人点赞 2020-01-05 16:32:02
    1基本原理 冒泡排序是一种稳定排序,时间复杂度平均为O(n^2),最好的时间复杂度为O(n),最...每次大排列中都要比较当前元素与后一个元素的大小,每轮要比较n-1次,但是因为之前的每一轮都将一个元素放置到了正确的...

     

    目录

     

    1 基本原理

    2 C语言程序

    3 博主的闲聊群


    1 基本原理

    冒泡排序是一种稳定排序,时间复杂度平均为O(n^2),最好的时间复杂度为O(n),最坏为O(n^2)。

    排序时每次只比较当前元素与后一个 元素的大小,如果当前元素大于后一个元素,则交换,如此循环直到队尾,每轮排序都可以保证将当前排序下最大的元素送到未排序部分的队尾。

    每次大排列中都要比较当前元素与后一个元素的大小,每轮要比较n-1次,但是因为之前的每一轮都将一个元素放置到了正确的位置,所以无需比较,若设之前累计循环了i次,将i个元素正确地放置在了数组的末尾,所以每轮大排列只需要比较n-1-i次。

    冒泡排序,用一句话来总结:

    一组数中,相邻的两个数进行比较、交换,将最大(小)数交换至尾(首)部,即完成了一次冒泡排序。

    2 C语言程序

    /**冒泡排序
     *升序
     */
    void BubbleSort(int arr[],int len)
    {
     int i,j;
     int tem;
     for(i=len-1;i>0;i--)
     {
         for(j=0;j<i;j++)
         {
            if(arr[j]>arr[j+1])
            {
                tem = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tem;
            }
         }
     }
    
    }

    3 博主的闲聊群

    QQ:701359719

    展开全文
  • 概述排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 我们这里说说八大排序就是内部排序。 当n较大,...
  • 一、选择排序(Selection sort)是一种简单直观的排序算法,且是一种不稳定的排序方法。 二、选择排序(Selection sort)的实现原理: 排序的一组数中,选出最小(或最大)的一个数与第一个位置的数交换;在剩下的...
  • 源码地址 GitHub:https://github.com/GYT0313/C-DataStructure/blob/master/sortIn5.c包括:冒泡排序快速排序选择排序插入排序希尔排序运行:注意:快速排序的核心代码应该没有问题,但是不知道为什么链表长度的值...
  • C语言排序的几种算法

    千次阅读 2022-02-26 20:45:37
    C语言排序方法有三种, 一是冒泡排序法 通过双循环不断的比较,交换位置,将需要排序的元素一点一点向两侧移动,逐渐达到排序的目的 代码如下: for (j = 0; j < n; j++) { for (i = 0; i < n- j; i++) if ...
  • 1、冒泡排序*///冒泡 时间复杂度O(n^2)/*第一次:从一个数组的最后一个元素到该数组的第一个元素进行扫描,比较后一个元素与前一个元素的大小,如果后一个小于前一个,交换顺序。通过这样的交换,那么我们就可以把该...
  • 十大排序算法——桶排序C语言

    千次阅读 2020-05-18 16:29:10
    排序(稳定的排序算法) 桶排序 (Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)...
  • C语言实现排序算法

    2022-04-01 21:09:24
    这里实现几种常见的排序算法: 一、插入排序 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 1.1 直接插入排序 当插入第i个元素时,前面...
  • 基本思想:插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置,直到全部插入完毕。 void insertSort(vector<int>& nums) { int k = 0; for (int i = 0; i ...
  • 冒泡排序算法C语言

    2020-12-23 16:53:49
    冒泡排序算法C语言版 1、算法思想 冒泡排序就是将大的元素往后移动,类似排队排成一列,从前往后进行n轮遍历,每次从最前面的人开始,将他和他身后的人比较,高的站后面。然后第二个人和第三个人继续比较,高的站...
  • C语言算法-排序

    2021-05-25 05:08:58
    C语言算法-排序环境PC环境:Windows10 64bitIDE:sublime text3注:sublime text3需要安装C/C++编译环境处理选择排序特点:简单、容易实现缺点:执行速度慢实现过程:通过遍历的方式进行比较,找出数据中最小的(或...
  • 文章目录前言基于插入的排序算法直接插入排序希尔排序基于选择的排序算法直接选择排序排序冒泡排序分治类排序算法快速排序归并排序计数排序(非比较排序) 前言 这几天耗费了大量的时间去理清排序算法的实现以及...
  • 继续开始对排序算法进行整理。 一、希尔排序 希尔排序是D.L.Shell于1959年所提出的一种改进插入排序算法,在这之前排序算法的时间复杂度基本都是O(n2)O(n^2)O(n2),希尔排序是突破这个时间复杂度的第一批算法之一。 ...
  • 算法篇】排序——快速排序c语言) 核心思想 排序算法的思想非常简单,在待排序的数列中,首先要找一个数字作为基准数(这只是个专用名词)。为了方便,我们一般选择第 1 个数字作为基准数(其实可以随便选)。...
  • C语言实现八大排序算法(一)

    万次阅读 多人点赞 2019-04-05 15:21:33
    本文主要介绍数据结构中常见的八大排序算法,冒泡排序、快速排序、直接插入排序、希尔排序、简单选择排序、堆排序、归并排序和基数排序排序相描述 排序分类:若排序过程中,所有的文件都是放在内存中处理的,不...
  • 快速排序算法c语言实验报告实验六:冒泡法排序 物理学416班赵增月F12XX日期:XX年10月31日 一·实验目的1.熟练掌握程序编写步骤; 2.学习使用冒泡法和选择法排序; 3.熟练掌握数组的定义和输入输出方法。 二·...
  • 快速排序是由东尼·...递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。
  • 算法C语言实现 (第1-4部分)基础知识、数据结构、排序及搜索(原书第3版) 本书是Sedgewick彻底修订和重写的C算法系列的第一本。全书分为四部分,共16章。第一部分“基础知识”(第1—2章)介绍基本算法分析原理。...
  • #include int NumChange(int n){char s[6];char c1,c2;int i,j,r;itoa(n,s,10);for(i=0;i<5;i++){c1=s[i];for(j=i+1;j<5;j++)if(s[j]>c1){c2=c1;c1=s[j];s[j]=c2;}s[i]=c1;}r = atoi(s);...main(){...
  • 1.要求输入10个整数,从大到小排序输出输入:2 0 3 -4 8 9 5 1 7 6输出:9 8 7 6 5 3 2 1 0 -4解决方法:选择排序法实现代码如下:#include int main(int argc, const char * argv[]) {int num[10],i,j,k,l,temp;...
  • 关于栈的注意事项 关于异常处理: 如你所见,栈的异常处理是非常冗长累赘的,但我们也不能将之抛弃,《数据结构与算法分析C语言描述》中原文的描述是这样的: 对空栈进行的Pop或Top操作一般被认为是ADT的错误。...
  • c语言合并排序算法_合并排序算法

    千次阅读 2020-07-28 22:29:17
    c语言合并排序算法 合并排序算法 (Merge Sort Algorithm) Merge Sort follows the rule of Divide and Conquer to sort a given set of numbers/elements, recursively, hence consuming less time. 合并排序遵循...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 41,554
精华内容 16,621
关键字:

大小排序算法 c语言