【数据结构】【排序】其实超级简单啦！-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构】【排序】其实超级简单啦！。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

本博客的所有代码都已测试完毕，请放心使用哟❤
在文章的最后面会贴出全部的码源，各位行行好点个赞吧（小狗哭泣）QAQ

一、排序的概念及其运用

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<n; 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);
}

快速排序的特性总结：

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

最后的知识点咯！

我们前面的快排都是递归实现的，那么该如何实现非递归呢？
我们需要用栈来实现！
//没有栈的小伙伴我可以…额发一份出来，制作不易还请不要辜负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<stdio.h>
#include<stdlib.h>
#include<time.h>

void 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<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

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;
}