【数据结构】【排序】其实超级简单啦！

分类:热门推荐日期:2024-04-13浏览:1评论:0

本博客的所有代码都已测试完毕，请放心使用哟❤

在文章的最后面会贴出全部的码源，各位行行好点个赞吧（小狗哭泣）QAQ

【数据结构】【排序】其实超级简单啦！

  • 一、排序的概念及其运用
    • 1.1 排序的概念
    • 1.2 常见的排序算法
    • 二、常见的排序算法
      • 2.1插入排序
        • 1.直接插入排序
        • 2.希尔排序
        • 2.2 选择排序
          • 1.选择排序
          • 2. 堆排序
          • 2.3 交换排序
            • 1.冒泡排序
            • 2.快速排序（※重点）
            • 最后最后，代码汇总咯！（撒花~❀）

              一、排序的概念及其运用

              1.1 排序的概念

              排序：所谓排序，就是使一串记录，按照其中的某个的某个或者某些关键字的大小，递增或递减的排序起来的操作。

              内部排序：数据元素全部放在内存中的排序。

              外部排序：数据元素太多导致不能同时放在内存中，根据排序的要求不能在内外存之间移动的数据的排序。

              这个就只是概念，话不多说我们直接开始吧！

              1.2 常见的排序算法

              看着蛮多的，但是没关系，让我们来逐一击破！

              二、常见的排序算法

              首先首先：在最开始的时候我们要理解一下函数！

              非常重要！！

              注意：本次排序都是以增序的基础写的

              //交换
//在所有排序中，元素的交换是非常频繁的，所以在这里先包装，后续交换就可以直接引用
void Swap(int *p1, int*p2)
{ int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}
//打印 -> 将数组里的数全部打印出来
void PrintArray(int* a, int n)
{ for(int i = 0; i printf("%d", a[i]);
    }
    printf("\n");
}

              2.1插入排序

              基本思想 ：相比都玩过扑克牌吧，插入排序就跟扑克牌一样，运用到了排序思想，将一个个元素插入到 已排入的有序序列中。

              1.直接插入排序

              ⭐以 下 为 动 图 展 示 ⬇：

              ⭐ 代 码 实 现 ⬇

              //直接插入
void InsertSort(int* a, int n) { //我们假设一个end的位置
   //我们希望在[0,end]的范围中，从 end+1 下标的元素往前插入
   //end 往前遍历
   for (int i = 0; i < n - 1; i++){ //套一层循环控制 end 的起始位置
   	int end = i;
   	int tmp = a[end + 1];  //把后一个数据保存起来，因为在排序过程中前面的数会往后覆盖
   	while (end >= 0)
   	{ //如果tmp里面的值小于的话，那么就继续往前移动
   		if (tmp < a[end]){ a[end + 1] = a[end];
   			--end;
   		}else{//如果比他大就直接放在该下标的后一个位置
   			break;
   		}
   	}
   	//将插入的代码放到循环体外面是为了防止 tmp 要插入到数组首元素而导致end为-1
   	//这样循环就进不去了
   	a[end + 1] = tmp;
   }
}
              直接插入排序的特性总结：
              1.元素集合越接近有序，直接插入排序算法的时间效率越高
              2.时间复杂度O(N^2)
              3.空间复杂度O(1) 👉 他是一个稳定的排序算法 👈
              4.稳定性： 稳定

              2.希尔排序

              希尔排序法又称缩小增量法。

              希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。

              然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

              其中：gap为间距

              间距为gap的分为一组，对每一组执行插入排序

              ⭐以 下 为 动 图 展 示 ⬇：

              我们可以很明显的看到，其实希尔排序的代码和直接插入排序大差不差的。 直接插入中的间距时1 ，所以是+1 然而希尔排序的间距是 gap ，所以是+ gap

              //这一组完成的是一组的插入排序
void ShellSort(int* a, int n)
{int gap = 3;
	for (int i = 0; i < n-gap; i += gap)
	{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;
	}
	
}

              可以对比一下两端代码的区别

              但是这样排序只能接近有序，但并不是完全有序

              ⭐ 代 码 实 现 ⬇

              //ShellSort函数实现
void ShellSort(int* a, int n)
{ int gap = n; //初始间隔为数组长度
    while (gap > 1) //只要间隔大于1
    { gap = gap / 3 + 1; //将间隔缩小为原来的1/3
        for (int 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; //将元素插入到当前位置
        }
        //PrintArray(a, n); //打印排序后的数组
    }
}
              希尔排序的特性总结
              1.希尔排序是对直接插入排序的优化。
              2.当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就

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

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

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

              2.2 选择排序

              基本思想：

              每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

              1.选择排序

              选择排序:

              ⭐在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素

              ⭐若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换

              ⭐在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

              ⭐以 下 为 动 图 展 示 ⬇：

              他的核心思想是遍历一遍时将最小的筛选出来，然而我们可以改良，不仅将最小的选出来，也可以将最大的选出来

              ⭐ 代 码 实 现 ⬇

              //选择排序
void SelectSort(int* a, int n)
{ //注意的是，我们交换的是数组的下标而不是数组的元素哟
	int begin = 0, end = n - 1;  //给数组的两端分别定义begin和end，小的放左边，大的放右边
	while (begin < end) //循环结束的条件
	{ int mini = begin, maxi = begin; //定义一个最小值和一个最大值
		for (int i = begin; i <= end; i++)
		{if (a[i] < a[mini])
			{mini = 1;
			}
			if (a[i] > a[maxi])
			{maxi = i;
			}
		}
		Swap(&a[begin], &a[mini]);//最小值跟左边换，最大值跟右边换
		if (maxi == begin)  // 防止begin和maxi重叠后发生的双重交换
		{ //说明maxi被换到了mini
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);
		++begin;
		--end;  //每一次遍历之后都要缩小范围然后继续遍历
	}
}
              选择排序的特性总结
              1.直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
              2.时间复杂度：O(N^2)
              3.空间复杂度：O(1)
              4.稳定性：不稳定

              2. 堆排序

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

              👉总的来说： 利用堆删除思想来进行排序

              ⭐以 下 为 动 图 展 示 ⬇：

              ⭐ 代 码 实 现 ⬇

              //堆排序
void AdjustDown(int* a, int n, int parent)
{ int child = parent * 2 + 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 = parent * 2 + 1; //重新获取父节点的子节点
        }
        else //如果子节点已经比父节点大或相等了，说明父节点已经是最大值了
        { break; //结束循环
        }
    }
}
void HeapSort(int* a, int n)
{ // a数组直接建堆O(N)
    for (int i = (n - 1 - 1) / 2; i >= 0; --i) //从最后一个非叶子节点开始，逐个向下调整堆
    { AdjustDown(a, n, i); //调用调整函数
    }
    int end = n - 1; //排序的最后一个位置
    while (end > 0) //只要还有待排序的元素
    { Swap(&a[0], &a[end]); //将堆顶元素和最后一个元素交换
        AdjustDown(a, end, 0); //重新调整堆
        --end; //下一个待排序元素
    }
}

              2.3 交换排序

              1.冒泡排序

              其核心是每一次遍历都会将最大的值排在后面，就像冒泡了一样。

              ⭐以 下 为 动 图 展 示 ⬇：

              ⭐ 代 码 实 现 ⬇

              //冒泡排序
void BubbleSort(int* a, int n) 
{ //由于每一次遍历都排完了一个元素
	//所以在这里每一次的最后一个元素的下标都要-1
	for (int j = 0; j < n - 1; j++)
	{//注意：在这里给 i = 1 是为了后续与前一个元素进行比较，不会越界访问
		for (int i = 1; i < n - j; i++)
		{if (a[i - 1] > a[i])
			{ //交换
				Swap(&a[i - 1], &a[i]);
			}
		}
	}
}

              👉在以上冒泡排序的代码实现过程中，我们仍然可以优化 👈 ：

              当我们在一次遍历过程中，没有发生数据交换，那么说明已经排序完毕，可以直接退出

              在这里我们可以定义一个 exchange=1 如果发生交换则 exchange=0

              当遍历一遍后 if 满足 exchange=1 则没有发生交换：

              ⭐ 优 化 后 代 码 实 现 ⬇

              //冒泡排序
void BubbleSort(int* a, int n) 
{ for (int j = 0; j < n - 1; j++)
	{int exchange = 0;
		for (int i = 1; i < n - j; i++)
		{if (a[i - 1] > a[i])
			{ Swap(&a[i - 1], &a[i]);
				exchange = 1; //交换后为1
			}
		}
		if (exchange == 0)
			break;
	}
}
              冒泡排序的特性总结：
              1.冒泡排序是一种非常容易理解的排序
              2.时间复杂度：O(N^2)
              3.空间复杂度：O(1)
              4.稳定性：稳定

              2.快速排序（※重点）

              基本思想：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

              ⭐以 下 为 动 图 展 示 ⬇：

              注意： 我们可以看到，下面在第一遍遍历的时 候，数值 6 刚好就排到了数组的第六个位置

              👉因为在左右指针遍历的时候：p点为 6， 所有比p点小的都换到了左边，所以在最后 L == R 时，左边全是小于** 6** ，右边都是小于6 。于是6 就被换到了 正确的位置

              看了动图是否感觉还有些茫然，不着急，下面有代码的大纲，尝试去理解一下

              / 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int array[], int left, int right)
{ if(right - left <= 1)
 return;
 
 // 按照基准值对array数组的 [left, right)区间中的元素进行划分
 int div = partion(array, left, right);
 
 // 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
 // 递归排[left, div)
 QuickSort(array, left, div);
 
 // 递归排[div+1, right)
 QuickSort(array, div+1, right);
}

              🔺快速排序也需要用到递归展开图哟

              ==当我们直接实现代码的话可能会忽略一些细节！

              👇以下是一些重要的需要注意的：

              1. 二者相遇会分两种情况

              ⭐ L 遇 R ：R 先走， R 在比 key 小的位置停下来， L 没有找到比 key 大的，就会和 R 相遇，则 ➡️ 相遇位置就是 R 停下来的位置， 是比 key 小的位置

              》

              ⭐ R 遇 L ：第一轮以后的，先交换了， L 位置小于 key， 位置的值大于 key， R 启动找小，没有找到，与 L 相遇，则 ➡️ 相遇位置就是 R 停下来的位置， 是比 key 小的位置

              第一轮R遇L，那么就是R没有找到小的，直接就一路左移，遇到L， 也就是 key 的位置

              ⭐ 代 码 实 现 ⬇

              //快速排序
void QuickSort(int* a, int left, int right)
{ //我们一般会选择右边先走，所以代码实现统一以右边先走为例子
	if (left >= right)
		//如果区间不存在或者只有一个数了，那就不需要排序了，直接返回
		return; 
	int keyi = left;
	int begin = left, end = right;
	while (left < right)
	{//right 先走，找小的
		while (a[right] > a[keyi])
		{--right;
		}
		//left再走，找大
		while (a[left] > a[keyi])
		{++left;
		}
		//当左边找到比key大的，右边找到比key小的
		// 跳出循环时说明已经找到，交换即可
		Swap(&a[left], &a[right]); 
	}
	Swap(&a[left], &a[keyi]);
	keyi = left;
	// [begin, keyi-1] keyi [keyi+1, end]
	//由于我们需要使用递归来完成排序，所以左右的下标一定要记清楚
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

              ❓ 但是这里会有一个弊端，就是当数组是有序的时候，是最坏的情况

              因为每一次的都会是最左边那个值确定，那么就要递归数组长度次数，这就是最坏的情况O(N^2)

              👇有两种优化的方法：

              1.随机数选择 key

              void QuickSort1(int* a, int left, int right) {if (left >= right)
		return;
	int keyi = left;
    int begin = left, end = right;
	//注意，优化后的快排是为了应对数组是有序时造成的最坏情况
	//--------begin----------
	int randi = rand();  //设置一个随机值做 key
	randi %= (right - left); //取模之后，随机值就会固定在这个区间里面
	randi += left;  
	//加上 left 是为了确保下标在正确的区间内（因为区间的下标不一定从零开始，也有可能从 key 的边开始）
	Swap(&a[left], &a[randi]);
	//---------end-----------
	while (left < right)
	{//right 先走，找小的
		while (a[right] > a[keyi])
		{--right;
		}
		//left再走，找大
		while (a[left] > a[keyi])
		{++left;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[keyi]);
	keyi = left;
	
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

              2.三数取中

              顾名思义，是指三个数选取大小中等的数为 key

              left mid right

              int GetMidi(int* a, int left, int right)
{ int mid = (left + right)/2;
    if(a[left) < a[mid]
    { if(a[mid] < a[right])
        { return mid;
        }
        else if(a[left] > a[right])
        { return left;
        }
        else
        { return right;
        }
    }
    else  //a[left] > a[mid]
    { if(a[mid] > a[right]
        { return mid;
        }
        else if(a[left] > a[right])
        { return right;
        }
    }
}
//不过一般都不会用这种方法，所以我就放一个伪代码在这里

              当然当然啦，如果你觉得这个快排很复杂，没关系！下面有前后指针版本的快排，代码实现也很简单❤

              ⭐以 下 为 动 图 展 示 ⬇：

              具体实现方法：

              1、 cur > key 👉 ++cur

              2、 cur < key 👉 ++prev, 交换prev和cur的位置的值

                1. prev 紧跟 cur 一前一后
                1. prev 和 cur 之间是比 key 大的值

                ⭐ 代 码 实 现 ⬇

                void QuickSort2(int* a, int left, int right) 
{//指针实现！
	int keyi = left;
	int prev = left;
	int cur = left + 1;
	while (cur < right)
	{if (a[cur] < a[keyi] && ++prev != cur)
			Swap(&a[prev], &a[cur]);
		
		cur++;
	}
	Swap(&a[keyi], &a[prev]);
	keyi = prev;
    // [left, keyi-1] keyi [keyi+1, right]
    //由于我们需要使用递归来完成排序，所以左右的下标一定要记清楚
    QuickSort(a, left, keyi - 1);
    QuickSort(a, keyi + 1, right);
}

                快速排序的特性总结：

                1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
                2. 时间复杂度：O(N*logN)
                3. 空间复杂度：O(logN)
                4. 稳定性：不稳定

                最后的知识点咯！

                我们前面的快排都是递归实现的，那么该如何实现非递归呢？

                我们需要用栈来实现！

                //没有栈的小伙伴我可以…额发一份出来，制作不易还请不要辜负QAQ

                取栈顶区间，单趟排序，右左子区间入栈

                ⭐ 代 码 实 现 ⬇

                void QuickSortNonR(int* a, int left, int right)
{ //非递归
	Stack st;  //这里要引用栈的头文件
	
	StackInit(&st);
	StackPush(&st, left);
	StackPush(&st, right);
	while (StackEmpty(&st) != 0)
	{right = StackTop(&st);
		StackPop(&st);
		left = StackTop(&st);
		StackPop(&st);
		if (right - left <= 1)
			continue;
		int div = PartSort1(a, left, right);
		// 以基准值为分割点，形成左右两部分：[left, div) 和 [div+1, right)
		StackPush(&st, div + 1);
		StackPush(&st, right);
		StackPush(&st, left);
		StackPush(&st, div);
	}
	StackDestroy(&s);
}

                最后最后，代码汇总咯！（撒花~❀）

                真不容易啊，写到这里，凌晨的我发出了欣慰但又有一点虚弱的笑容：）

                我们将各个的排序进行比较

                sort.h

                #pragma once
#include#include#includevoid PrintArray(int* a, int n);
void InsertSort(int* a, int n);//直接插入
void ShellSort(int* a, int n);//希尔排序
void SelectSort(int* a, int n);//选择排序
void HeapSort(int* a, int n);//堆排序
void BubbleSort(int* a, int n);//冒泡排序
void QuickSort(int* a, int left, int right);//快速排序

                sort.c

                #include"sort.h"
//交换
void Swap(int* p1, int* p2)
{int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//打印
void PrintArray(int* a, int n) {for (int i = 0; i < n; i++)
	{printf("%d ", a[i]);
	}
	printf("\n");
}
//直接插入
void InsertSort(int* a, int n) {//我们假设一个end的位置
	//我们希望在[0,end]的范围中，从 end+1 下标的元素往前插入
	//end 往前遍历
	for (int i = 0; i < n - 1; i++){ //套一层循环控制 end 的起始位置
		int end = i;
		int tmp = a[end + 1];  //把后一个数据保存起来，因为在排序过程中前面的数会往后覆盖
		while (end >= 0)
		{ //如果tmp里面的值小于的话，那么就继续往前移动
			if (tmp < a[end]){a[end + 1] = a[end];
				--end;
			}else{//如果比他大就直接放在该下标的后一个位置
				break;
			}
		}
		//将插入的代码放到循环体外面是为了防止 tmp 要插入到数组首元素而导致end为-1
		//这样循环就进不去了
		a[end + 1] = tmp;
	}
}
//希尔排序
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 tmp = a[end + gap];
			while (end >= 0)
			{if (tmp < a[end])
				{a[end + gap] = a[end];
					end -= gap;
				}
				else
				{break;
				}
			}
			a[end + gap] = tmp;
		}
		//PrintArray(a, n);
	}
}
//-----------------------------------
//选择排序
void SelectSort(int* a, int n)
{ //注意的是，我们交换的是数组的下标而不是数组的元素哟
	int begin = 0, end = n - 1;  //给数组的两端分别定义begin和end，小的放左边，大的放右边
	while (begin < end) //循环结束的条件
	{ int mini = begin, maxi = begin; //定义一个最小值和一个最大值
		for (int i = begin; i <= end; i++)
		{if (a[i] < a[mini])
			{mini = 1;
			}
			if (a[i] > a[maxi])
			{maxi = i;
			}
		}
		Swap(&a[begin], &a[mini]);//最小值跟左边换，最大值跟右边换
		if (maxi == begin)  // 防止begin和maxi重叠后发生的双重交换
		{ //说明maxi被换到了mini
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);
		++begin;
		--end;  //每一次遍历之后都要缩小范围然后继续遍历
	}
}
	
//堆排序
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 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 = parent * 2 + 1;
		}
		else
		{break;
		}
	}
}
void HeapSort(int* a, int n)
{// a数组直接建堆O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{AdjustDown(a, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

//----------------------------------------
//冒泡排序
void BubbleSort(int* a, int n) 
{ //由于每一次遍历都排完了一个元素
	//所以在这里每一次的最后一个元素的下标都要-1
	for (int j = 0; j < n - 1; j++)
	{int exchange = 0;
		//注意：在这里给 i = 1 是为了后续与前一个元素进行比较，不会越界访问
		for (int i = 1; i < n - j; i++)
		{if (a[i - 1] > a[i])
			{ //交换
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}
		if (exchange == 0)
			break;
	}
}
//快速排序
void QuickSort(int* a, int left, int right)
{ //我们一般会选择右边先走，所以代码实现统一以右边先走为例子
	if (left >= right)
		//如果区间不存在或者只有一个数了，那就不需要排序了，直接返回
		return; 
	int keyi = left;
	int begin = left, end = right;
	while (left < right)
	{//right 先走，找小的
		while (a[right] > a[keyi])
		{--right;
		}
		//left再走，找大
		while (a[left] > a[keyi])
		{++left;
		}
		//当左边找到比key大的，右边找到比key小的
		// 跳出循环时说明已经找到，交换即可
		Swap(&a[left], &a[right]); 
	}
	Swap(&a[left], &a[keyi]);
	keyi = left;
	// [begin, keyi-1] keyi [keyi+1, end]
	//由于我们需要使用递归来完成排序，所以左右的下标一定要记清楚
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}
void QuickSort1(int* a, int left, int right) 
{if (left >= right)
		return;
	int keyi = left;
    int begin = left, end = right;
	//注意，优化后的快排是为了应对数组是有序时造成的最坏情况
	//--------begin----------
	int randi = rand();  //设置一个随机值做 key
	randi %= (right - left); //取模之后，随机值就会固定在这个区间里面
	randi += left;  
	//加上 left 是为了确保下标在正确的区间内（因为区间的下标不一定从零开始，也有可能从 key 的边开始）
	Swap(&a[left], &a[randi]);
	//---------end-----------
	while (left < right)
	{//right 先走，找小的
		while (a[right] > a[keyi])
		{--right;
		}
		//left再走，找大
		while (a[left] > a[keyi])
		{++left;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[keyi]);
	keyi = left;
	
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}
void QuickSort2(int* a, int left, int right) 
{//指针实现！
	int keyi = left;
	int prev = left;
	int cur = left + 1;
	while (cur < right)
	{if (a[cur] < a[keyi] && ++prev != cur)
			Swap(&a[prev], &a[cur]);
		
		cur++;
	}
	Swap(&a[keyi], &a[prev]);
	keyi = prev;
	// [left, keyi-1] keyi [keyi+1, right]
	//由于我们需要使用递归来完成排序，所以左右的下标一定要记清楚
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi + 1, right);
}	
#include"Stack.h"
void QuickSortNonR(int* a, int left, int right)
{ //非递归
	ST st;
	StackInit(&st);
	StackPush(&st, left);  //先把当先的区间录进去
	StackPush(&st, right);
	while (StackEmpty(&st) != 0)  //如果栈不为空就继续
	{right = StackTop(&st);  
		StackPop(&st);
		left = StackTop(&st);
		StackPop(&st);
		if (right - left <= 1)
			continue;
		int div = PartSort1(a, left, right);
		// 以基准值为分割点，形成左右两部分：[left, div) 和 [div+1, right)
		StackPush(&st, div + 1);
		StackPush(&st, right);
		StackPush(&st, left);
		StackPush(&st, div);
	}
	StackDestroy(&st);
}

                后面就是栈所需要的代码源，用来实现非递归的快排的前情提要

                //stack.h
#pragma once
#include#include#include#include
typedef int STDataType;
typedef struct Stack
{STDataType* a;
	int top;
	int capacity;
}ST;
void STInit(ST* ps);
void STDestroy(ST* ps);
void STPush(ST* ps, STDataType x);
void STPop(ST* ps);
STDataType STTop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);
//stack.c
#include"Stack.h"
void STInit(ST* ps)
{assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}
void STDestroy(ST* ps)
{assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}
void STPush(ST* ps, STDataType x)
{assert(ps);
	// ˣ 
	if (ps->top == ps->capacity)
	{int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{perror("realloc fail");
			return;
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}
void STPop(ST* ps)
{assert(ps);
	assert(!STEmpty(ps));
	ps->top--;
}
STDataType STTop(ST* ps)
{assert(ps);
	assert(!STEmpty(ps));
	return ps->a[ps->top - 1];
}
int STSize(ST* ps)
{assert(ps);
	return ps->top;
}
bool STEmpty(ST* ps)
{assert(ps);
	return ps->top == 0;
}

                创作不易，还请多多支持。

                谢谢（鞠躬）

相关推荐

关于我们常见问题广告服务免责声明联系我们
Powered By Z-BlogPHP 1.7.3 Theme By 优美主题
Copyright Your WebSite.Some Rights Reserved. 浙ICP备2023018783号