前言：本章将介绍常见八大排序包括如下直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快排、归并排序以及计数排序（基数排序和桶排序面试基本不涉及，本文忽略了，有兴趣的读者可以自行补充），本章内容是重点中的重点！！！铁子们务必全部掌握！！！

1.插入排序

1.1直接插入排序

基本思想
把一个数插入到有序区间，保持这个区间有序，当前第n+1个数插入到前面，前面的arr[0]到arr[n-1]已经排好序，此时用arr[n]与前面的arr[n-1], arr[n-2]…的值。进行比较找到合适的位置将arr[n]进行插入，原来位置上的元素顺序后移实现了插入

代码实现

//插入排序
void InsertSort(int* a, int n){
    //控制起始条件
    //注意控制好终止条件，这里的end的位置是在倒数第二个位置，所以要-1
    for(int i=0; i<n-1;i++){ 
        //单趟插入
        int end = i;
        int temp = a[end + 1]; //有序区间的后面
        while(end>=0){ //end到-1就终止了
            if(a[end]>temp){
                a[end+1] = a[end];
                --end;
            }else{
                break;
            }
        }
        //两种情况：第一种在最右边，第二种在最左边，end为-1了，始终放在end后面
        a[end+1] = temp;    
    }
}

时间复杂度

插入排序的时间复杂度也是O（N^2）,在接近有序的情况下他的时间复杂度是O（N），因为遍历一遍就可以出结果了，空间复杂度O（1）。

1.2希尔排序

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

基本思想
希尔排序就是在处理一些极端情况比较高效，比如在上面的插入排序时如果我们在原数组降序的情况下去排升序，那么我们交换的次数是十分多的，也可以说是插入排序的最坏的情况，这个时候聪明的先辈想到了希尔排序，将数组分成了gap组，然后可以理解为分别处理每一个小组，gap从5 – 2 – 1的过程在降序的情况下，排在后面的数值小的数能步子更大排到前面，当gap为1的时候实际上就是进行了一次插入排序。设置gap的过程我们也称之为预排序。

gap越小，越接近有序，gap越大，越不接近有序；
但是gap越小挪动越慢，gap越大挪动越快；

代码实现

void ShellSort1(int* a, int n)
{
    int gap = n;
    while (gap>1)//别傻乎乎的加等号啊，死循环
    {
        gap = gap / 3 + 1;end的范围是[0,n-gap)
        
        for (int i = 0; i < n - gap; i++)//并排走
        {
            int end = i;
            int temp = a[end + gap];
            while (end>=0)
            {
                //当前的end的值比tmp大就要往end+gap位置挪
				//所以要提前保存end+gap的值
                if (temp < a[end])
                {
                    a[end + gap] = a[end];
                    end = end-gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = temp;
        }
    }
}

时间复杂度

O(N^1.3)，一般gap建议以gap/3+1的步骤走。

2.选择排序

简单选择排序思路如下动图所示，就是只针对头部的一个数进行对比，代码实现大家可以自己敲敲！

2.1 选择排序（二元改进版）

基本思想
优化的选择排序，每次可以选择一个最大的和一个最小的，然后把他们放在合适的位置，即最小的放在第一个位置，最大的放在最后一个位置。
然后再去选择次小的和次大的，依次这样进行，直到区间只剩一个值或没有。

代码实现

void SelectSort(int* a, int n)
{
	assert(a);
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int min = begin, max = begin;
		for (int i = begin; i <= end; i++)//注意起点是begin
		{
			if (a[i] >= a[max])
				max = i;
 
 
			if (a[i] < a[min])
				min = i;
		}
		//最小的放在
		Swap(&a[begin], &a[min]);
		//如果最大的位置在begin位置
		//说明min是和最大的交换位置
		//这个时候max的位置就发生了变换
		//max变到了min的位置
		//所以要更新max的位置
		if (begin == max)
			max = min;
 
		Swap(&a[end], &a[max]);
		++begin;
		--end;
	}
}

时间复杂度

O(N^2)，最坏的排序

2.2 堆排序

堆排之前文章详细介绍过，具体细节欢迎点击查阅

基本思想
细节去查阅之前的文章，现在就强调一点：排升序要建大堆，排降序建小堆

这里以升序为例：先建堆，排升序建大堆，选出最大的数将其放到最后面，然后满足大小堆后即可做向下调整动作。

代码实现

//堆排序
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){
    //排升序建大堆 O(N)
    for(int i=(n-1-1)/2; i>=0; i--){
        AdjustDown(a, n, i);
    }
    
    //O(N*logN)
    int end = n - 1;
    while(end > 0){
        Swap(&a[0], &a[end]);
        AdjustDown(a, end, 0); //是不是妙不可言hhh！
        end--;
    }
}

记录下写堆排时犯的错误（读者可以跳过，这是留给作者复习自用的）：

边界问题，画图画图，冷静分析！！！

时间复杂度

时间复杂度是O（N/*logN），空间复杂度O（1）

3.交换排序

3.1 冒泡排序

基本思想
以升序为例，每一趟的冒泡排序都是把一个最大的数放到最后面，如果 a[i-1]>a[i],我们将i-1,i的值进行交换，依次循环反复。

代码实现

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

时间复杂度

O(N^2)

3.2 快速排序

3.2.1 Hoare

基本思想

选一个关键key，一般都是选择头。
单趟：key放在他正确的位置上，key的左边值比key小，key右边值比key大（这是key一趟下来排完后最终要放的位置）
单趟拍完，再想办法让左边区间有序，key的右边区间有序

那么还有优化解决方案：
第一种是取随机值做下标
第二种是获取这三个数中不是最大，也不是最小的那个值的下标，这种情况下不会有最坏情况，因为有三数组取中

代码实现

三数取中（为了优化）

//三数取中
int MidIndex(int* a, int left, int right)
{
	int mid = left + (right - left) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return right;
		}
		else
		{
			return left;
		}
	}
	else //a[left] > a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
//不妨思考一下我们进行“三数取中”的意义是什么？

单趟排序：

//一个单趟进行的排序操作的时间复杂度是多少？思考下一次完整的快排需要进行多少趟这样的单趟排序？
int PartSort1(int* a, int left, int right)
{
	int midi = MidIndex(a, left, right);
	Swap(&a[left], &a[midi]);
	//最左边的做key为例
	int key = left;
	while (left<right)
	{
		//因为我们是最左边的取key，所以必须是右边先走找比key小的，思考下为什么？
		//右边先走
		while (left < right && a[right] >= a[key])
		{
			--right;
		}
		//然后左边走
		while (left < right && a[left] < a[key])
		{
			++left;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[key]);//此时left已经和right相遇，一样的
	return left;
}

全趟排序（递归）：

void QuickSort(int* a, int left, int right)
{
	//当区间分割到只剩一个或者没有的时候就返回
	if (left >= right)
		return;
	//确定一个位置，划分区间递归
	//分为[left,key-1]   key   [key+1，right]
	//int key = PartSort1(a, left, right);
	int key = PartSort2(a, left, right);
	QuickSort(a, left, key - 1);
	QuickSort(a, key + 1, right);
}

第一个问题：不妨思考一下我们进行“三数取中”的意义是什么？

如果我们不进行“三数取中”，快排如果遇见最坏的情况——有序，时间复杂度将会变成O（N^2），如果加了“三数取中”，这一最坏情况将会不复存在（后边俩种单趟排序同理）。当然了，实际面试过程当中时间不够没必要再来写一个“三数取中”，面试争分夺秒啦！

第二个问题：一个单趟进行的排序操作的时间复杂度是多少？思考下一次完整的快排需要进行多少趟这样的单趟排序？

一个单趟的时间复杂度是O（N），一个完整的快排需要O（logN）趟这样的单趟排序。

第三个问题：为什么key选择最左边的值，就要先让右边的数先走先去找小？

为了确保最后相遇时的a[left]<a[key]，只要让右边的数先走，最后停下来时无论是“左边遇到右边”还是“右边遇到左边”，都满足a[left]<a[key]。

时间复杂度

一整个快排：O（N/*logN）

3.2.2 前后指针法

基本思想
1.cur往前走，找到比key小的数据

2.找到比key小的数据以后，停下来，++prev

3.交换prev和cur指向位置的值

直到cur到达最右边的位置结束！

cur还没遇到比key大的数据之前，prev紧跟着cur，cur遇到比key大的值以后，prev和cur之间间隔着一段比key大的数据。

代码实现

int PartSort2(int* a, int left, int right)
{
	int midi = MidIndex(a, left, right);
	Swap(&a[midi], &a[left]);
	//这里key选取最左边的元素为例
	int key = left;
	int prev = left, cur = prev + 1;
	while (cur<=right)
	{
		if (a[cur] < a[key] && ++prev != cur)//防止自己与自己交换
		{
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
    //cur走到末尾啦，交换一下。
	Swap(&a[prev], &a[key]);//这里可以保证交换之前a[prev]一定小于a[key],思考下为啥？
	return prev;
}

答案：跳出while循环的a[prev]，在跳出循环之前刚与a[cur]交换过，而a[prev]与a[cur]交换的条件就是a[cur]小于a[key],所以可以保证交换跳出while循环后发生最后一次交换之前a[prev]一定小于a[key]。

全趟排序（递归）：

void QuickSort(int* a, int left, int right)
{
	//当区间分割到只剩一个或者没有的时候就返回
	if (left >= right)
		return;
	//确定一个位置，划分区间递归
	//分为[left,key-1]   key   [key+1，right]
	//int key = PartSort1(a, left, right);
	int key = PartSort2(a, left, right);
	QuickSort(a, left, key - 1);
	QuickSort(a, key + 1, right);
}

时间复杂度

一整个快排：O（N/*logN）

3.2.3 挖坑法

基本思想
挖坑法可以选择在0索引处挖坑（即把数拿走保存），然后从右边找一个小的填坑，再从左边找一个大的埋住右边的坑，以此反复循环，直到left与right相遇，最后把key放入相遇点（最后一个坑位）即可。

代码实现

int PartSort3(int* a, int left, int right)
{
	int midi = MidIndex(a, left, right);
	Swap(&a[midi], &a[left]);
	//这里key取最左边的数，让右边的先开始走找小
	int hole = left;
	int key = a[left];
	while (left < right)
	{
		//先找右边比key小的，填到左边的坑里面去
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[hole] = a[right];
		hole = right;
		//再找左边比key大的，找到就交换坑位
		while (left<right&&a[left]<key)
		{
			left++;
		}
		a[hole] = a[left];
		hole = left;
	}
	a[left] = key;//最后把key放到相遇点
	return left;
}

全趟排序（递归）：

void QuickSort(int* a, int left, int right)
{
	//当区间分割到只剩一个或者没有的时候就返回
	if (left >= right)
		return;
	//确定一个位置，划分区间递归
	//分为[left,key-1]   key   [key+1，right]
	//int key = PartSort1(a, left, right);
	int key = PartSort3(a, left, right);
	QuickSort(a, left, key - 1);
	QuickSort(a, key + 1, right);
}

时间复杂度

一整个快排：O（N/*logN）

3.3 快速排序（非递归）

我们前面实现快排是采用递归的方式，但是递归本身是有“原罪”的，这个“原罪”在于如下：
1.当递归深度过大的时候，递归程序本身可能没用错误，但是编译之后会报错——栈溢出（stack overflow）。

2.性能问题（某些书上提到的，但是现在编译优化得很好，这个问题不大）。

任何一个递归程序，我们要把他改成非递归程序有如下俩种方式：

1.循环(但是有的东西是不好改成循环的，比如二叉树的遍历、快排等)

2.“栈”模拟（这个“栈”是数据结构中的“栈”，不是系统内部那个“栈”，一般用到栈难度都是略大的）

这里的快排改非递归用的就是“栈”模拟。

基本思想

非递归的在这里借助栈，依次把我们需要单趟排的区间入栈，依次取栈里面的区间出来单趟排，再把需要处理的子区间入栈，以此循环，直到栈为空的时候即处理完毕。

非递归代码实现

void QuickSortNonR(int* a, int left, int right)
{
	//非递归，我们可以处理当前的区间，再处理分区间
	//先入右，后入左，就先拿到左
	Stack s;
	StackInit(&s);
	StackPush(&s,right);
	StackPush(&s,left);
	while (!StackEmpty(&s))
	{
		left = StackTop(&s);
		StackPop(&s);
		right = StackTop(&s);
		StackPop(&s);
		//处理当前区间 [left,right]
		int key = PartSort3(a, left, right);
		//划分左右区间，分别入栈
		//[left,key-1] key [key+1,right]
		//先入右区间,区间有两个值才需要处理
		if (key + 1 < right)
		{
			StackPush(&s, right);
			StackPush(&s, key + 1);
		}
		//再入左区间
		if (left < key - 1)
		{
			StackPush(&s, key - 1);
			StackPush(&s, left);
		}
	}	
}

时间复杂度

最优的时间复杂度是O(nlogn)，最差的空间O(n^2) ，因为进行了三数取中，不存在最差情况。

4.归并排序

4.1 递归实现归并排序

基本思想
我们可以把一个数组分成两半，对于每一个数组当他们是有序的就可以进行一次合并操作。对于他们的两个区间进行递归，一直递归下去划分区间，当区间只有一个值的时候我们就可以进行合并返回上一层，让上一层合并再返回。

代码实现

void _MergeSort(int* a, int left, int right,int* newArr)
{
	if (left >= right)
		return;
	int mid = left + (right - left) / 2;
	//[left,mid][mid+1,right]
	_MergeSort(a, left, mid,newArr);
	_MergeSort(a, mid + 1, right,newArr);
	//走到这里已经是左右区间有序
	//将两个区间合并成一个区间
	//拷贝到newArr当中，排完再放回
	int index = left;
	int begin1 = left, end1 = mid;
	int begin2 = mid+1,end2 = right;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			newArr[index++] = a[begin1++];
		}
		else
		{
			newArr[index++] = a[begin2++];
		}
	}
	//走到这里一定有一边没有走完
	while (begin1 <= end1)
	{
		newArr[index++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		newArr[index++] = a[begin2++];
	}
	//拷贝回元素组 letf -- right 的位置
	for (int i = left; i <= right; ++i)
	{
		a[i] = newArr[i];
	}
}
void MergeSort(int* a, int n)
{
//归并排序就是在左右区间有序重新组合起来
//所以保证左右区间都是有序，遍历到叶子就可以
	int* newArr = (int*)malloc(sizeof(int) * n);
	int left = 0;
	int right = n - 1;
	_MergeSort(a, left, right,newArr);
}

时间复杂度

O（NlogN)，可以看出他的递归过程中每次都将一组平均分，分完后高度大概是logN，空间复杂度O（N）

4.2 迭代实现归并排序

跟快排类似，递归会带给快排的问题同样会给归并排序带来，所以尝试用非递归方式！

任何一个递归程序，我们要把他改成非递归程序有如下俩种方式：
1.循环(但是有的东西是不好改成循环的，比如二叉树的遍历、快排等)

2.“栈”模拟（这个“栈”是数据结构中的“栈”，不是系统内部那个“栈”，一般用到栈难度都是略大的）

这里归并排序非递归实现就是采用“循环”。

基本思想

迭代实现可以用循环来实现，这里我们根据递归思想其实很容易知道，我们控制迭代从最小的子问题出发，保存最小子问题的值，然后提供给后面用，这其实就是一个动态规划的思想，我们可以从利用子问题的解，解决 “大BOSS” 。

代码实现

void MergeSortNonR(int* a, int n)
{
	//int a[] = { 8,4,5,7,1,3,6,2,7,8 };
	
	int* newArr=(int*)malloc(sizeof(int)*n) ;
	int groupNum = 1;
	int left;
	int right;
	//动态规划的思想，当我们把最小的问题切割
	while(groupNum<n/2+1)
	{
		for (int i = 0; i < n; i += (2*groupNum))
		{
		//分成两组[begin1,end1][begin2,end2]
		int begin1 = i;
		int end1 = i + groupNum - 1;
		int begin2 = i + groupNum;
		int end2 = i + 2 * groupNum - 1;
		//处理两种情况，当end1已经越界，说明处理end1的边界
		if (end1 >= n)
		{
			end1 = n - 1;
		}
		//当end1越界，理所当然的begin2和end2都越界了
		//这里可能的[begin1,end1]区间，也需要拷贝到临时数组，再拷回原数组
		if (begin2 >= n)
		{
			//表示右区间不存在
			begin2 = n;
			end2 = n-1;
		}
		else if (begin2 < n && end2 >= n)
		{
			end2 = n - 1;
		}
		left = begin1;
		right = end2;
		//index用于放到临时数组newArr当中的
		int index = begin1;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					newArr[index++] = a[begin1++];
				}
				else
				{
					newArr[index++] = a[begin2++];
				}
			}
			//走到这里一定有一边没有走完
			while (begin1 <= end1)
			{
				newArr[index++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				newArr[index++] = a[begin2++];
			}
			//拷贝回元素组 letf -- right 的位置
			for (int x = left; x <= right; ++x)
			{
				a[x] = newArr[x];
			}
		}
		groupNum*=2;
	}
	free(newArr);
	newArr = NULL;
}

时间复杂度

O（NlogN)

5.计数排序

基本思想
1.统计原数组中每个值出现的次数

2.排序：遍历Count数组，对应位置的值出现多少次就往原数组写几个这个值

当然，在对于数据比较大的时候我们可以通过相对映射，让（该值-min）后的数组加一，最后还原回去即可。

代码实现

void CountSort(int* a, int n)
{
	//int a[] = { 31,24,25,16,1,0,79 };
	//遍历一遍找到最大和最小，然后开大一的数组
	int max = a[0];
	int min = a[0];
	for (int i = 1; i < n; ++i)
	{
		if (max < a[i])
		{
			max = a[i];
		}
		if (min > a[i])
		{
			min = a[i];
		}
	}
	int size = max - min + 1;
	int* tmp = (int*)calloc(size,sizeof(int));
	//将a遍历映射到tmp当中,a的长度是n，tmp的长度只有size
	for (int i = 0; i < n; ++i)
	{
		tmp[a[i] - min]++;//tmp[i]存放的是这个值出现的次数
	}
	//在按照tmp当中的存放放回去
	int index = 0;
	for (int i = 0; i < size; ++i)
	{
		while (tmp[i] > 0)
		{
			//这里应该是下标+映射的
			a[index++] = i + min;
			--tmp[i];
		}
	}
}

时间复杂度

计数排序的时间复杂度是O（N），空间复杂度是O(max-min),就是我们开的数组是这个区间的范围差。

6.八大排序对比

6.1八大排序的性能测试评估

// 测试排序的性能对比
void TestOP()
{
srand(time(0));
const int N = 10000;
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);
int* a7 = (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];
    a7[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(a4, 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);
 free(a7);
 }

结果如下：

6.2 各个排序的稳定性如何判断？

直接看排完序后是否能保证相同的值的相对位置不会发生变化，若能保证，就是稳定，反之即不稳定。

不要死记，一定要理解分析！

冒泡排序：俩俩对比，前一个大于后一个才发生交换（升序），不会出现相等值互换顺序的情况，能保证不改变相同值的相对顺序，稳定。

简单选择排序：在进行俩数交换位置的过程当中，可能数组当中有一个数跟发生交换的俩数数值是一样的，这样就改变的相同数之间的相对顺序，不稳定。

直接插入排序：从前到后一个个元素拿出来跟前面的对比，若插入的数值比被对比的数值小，被对比的数值往后挪动；若插入的数值比被对比的数值大，直接插入到被对比数值的后面，并没有改变俩个相同值得相对顺序，稳定。

希尔排序：在预排序时，相同的数据可能在不同的组里面，没办法控制，所以不稳定。

堆排序：比如俩个一样大的数值，一个在“树顶”，一个在“树中”，树顶元素跟最后一个元素发生交换立马影响相同数值的相对顺序，不稳定。

归并排序：能保证相同值得相对顺序不变，稳定。

快速排序：比如数组中存在跟key数值一样的值，而key是肯定会移动的，这样相对顺序就改变了，所以不稳定。

计数排序：计数是在统计每个数出现的次数，但是相同的数哪个在前哪个在后，并没有区分，所以不稳定。

补充：稳定性有什么意义？

比如我们做了一个考试系统，考生当中先交卷的，成绩在数组的前面，后交卷的，成绩在数组后面。当我们对前几名进行排名的时候，就可能会遇见俩个分值相同的考生，这时候为了公平性考试用时较短者应当在前面。

两万字搞定《数据结构》八大排序必读（建议收藏）

1.插入排序

1.1直接插入排序

1.2希尔排序

2.选择排序

2.1 选择排序（二元改进版）

2.2 堆排序

3.交换排序

3.1 冒泡排序

3.2 快速排序

3.2.1 Hoare

3.2.2 前后指针法

3.2.3 挖坑法

3.3 快速排序（非递归）

4.归并排序

4.1 递归实现归并排序

4.2 迭代实现归并排序

5.计数排序

6.八大排序对比

6.1八大排序的性能测试评估

6.2 各个排序的稳定性如何判断？

6.3八大排序时间/空间复杂度一览

相关文章

热门标签

最新文章

目录

两万字搞定《数据结构》 八大排序 必读（建议收藏）

1.插入排序

1.1直接插入排序

1.2希尔排序

2.选择排序

2.1 选择排序（二元改进版）

2.2 堆排序

3.交换排序

3.1 冒泡排序

3.2 快速排序

3.2.1 Hoare

3.2.2 前后指针法

3.2.3 挖坑法

3.3 快速排序（非递归）

4.归并排序

4.1 递归实现归并排序

4.2 迭代实现归并排序

5.计数排序

6.八大排序对比

6.1八大排序的性能测试评估

6.2 各个排序的稳定性如何判断？

6.3八大排序时间/空间复杂度一览

相关文章

热门标签

最新文章

目录

两万字搞定《数据结构》八大排序必读（建议收藏）