【数据结构 — 排序 — 交换排序】

数据结构 — 排序 — 交换排序

  • 一.交换排序
    • 1.基本思想
    • 2.冒泡排序
      • 2.1.算法讲解
      • 2.2.代码实现
        • 2.2.1.函数定义
        • 2.2.2.算法接口实现
        • 2.2.3.测试代码实现
        • 2.2.4.测试展示
    • 3.快速排序
      • 3.1.算法讲解
      • 3.2.各大算法分别单独实现
        • 3.2.1快速排序hoare版本
        • 3.2.2.快速排序hoare改进版三数取中选key法
        • 3.2.3.快速排序hoare版本改进版小区间优化法
        • 3.2.4.快速排序挖坑法
        • 3.2.5.快速排序双指针法
        • 3.2.6.快速排序非递归版
      • 3.3.算法完整源码分享
        • 3.3.1函数定义
        • 3.3.2.算法接口实现
        • 3.3.3.测试代码实现
        • 3.3.4.测试展示

一.交换排序

1.基本思想

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

2.冒泡排序

2.1.算法讲解

以下只讲解冒泡排序代码的简单实现 ，想要更详细的了解冒泡排序的可以前往我之前的博客冒泡排序及其优化 （点击即可跳转），里面详细讲解了冒泡排序及其优化。

在这里插入图片描述

冒泡排序的特性总结：

  1. 冒泡排序是一种非常容易理解的排序
  2. 时间复杂度：O(N^2)
  3. 空间复杂度：O(1)
  4. 稳定性：稳定

2.2.代码实现

2.2.1.函数定义
Sort.h

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<string.h>
#include<time.h>


//打印
void PrintArray(int* a, int n);
//冒泡排序
void BublleSort(int* a, int n);
2.2.2.算法接口实现
Sort.c

#include"Sort.h"


void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//冒泡排序
void BublleSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int flag = 1;
		for (int j = 0; j < n - i - 1; j++)
		{
			if (a[j + 1] < a[j])
			{
				Swap(&a[j + 1], &a[j]);
				flag = 0;
			}
		}
		if (flag == 1)
			break;
	}
}
2.2.3.测试代码实现
test.c

#include"Sort.h"


void TestBublleSort()
{
	int a[] = { 2,4,5,7,8,0,9,6,3,1 };
	printf("排序前：");
	PrintArray(a, sizeof(a) / sizeof(int));
	printf("\n");
	printf("冒泡排序：");
	BublleSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

int main()
{
   TestBublleSort();
   
   return 0;
}
2.2.4.测试展示

在这里插入图片描述

3.快速排序

3.1.算法讲解

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

快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。

将区间按照基准值划分为左右两半部分的常见方式有：
1. hoare版本

在这里插入图片描述
2.hoare改进版
1. 三数取中法选key
2. 递归到小的子区间时，可以考虑使用插入排序
3.挖坑法
在这里插入图片描述
4.前后指针版本
在这里插入图片描述
5.非递归版
非递归需要借助栈来实现，将大区间划分成子区间的递归过程，需要循环实现，如果有小伙伴不懂栈的实现和使用，可以前往我之前的博客数据结构—— 栈的实现（数组栈）（点击即可跳转）了解栈的相关只是。
在这里插入图片描述

快速排序的特性总结：

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

3.2.各大算法分别单独实现

3.2.1快速排序hoare版本
Sort.h

//快速排序hoare版本
void QuickSortHoare(int* a, int begin, int end);

Sort.c

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//快速排序hoare版本
void QuickSortHoare(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	int left = begin, right = end;
	int keyi = begin;
	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}

		Swap(&a[left], &a[right]);
	}

	Swap(&a[left], &a[keyi]);
	keyi = left;

	QuickSortHoare(a, begin, keyi - 1);
	QuickSortHoare(a, keyi + 1, end);
}
3.2.2.快速排序hoare改进版三数取中选key法
Sort.h

//1.快速排序hoare改进版三数取中选key法
void QuickSortMid(int* a, int begin, int end);

Sort.c

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//三数取中
int GetMidi(int* a, int begin, int end)
{
	int midi = (begin + end) / 2;
	if (a[begin] < a[midi])
	{
		if (a[end] > a[midi])
			return midi;
		else if (a[end] < a[midi])
			return a[begin] > a[end] ? begin : end;

	}
	else if (a[begin] > a[midi])
	{
		if (a[end] < a[midi])
			return midi;
		else if (a[end] > a[midi])
			return a[begin] < a[end] ? begin : end;
	}
	return midi;

}

//1.快速排序hoare版本改进版三数取中选key法
void QuickSortMid(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	int midi = GetMidi(a, begin, end);
	Swap(&a[midi], &a[begin]);

	int left = begin, right = end;
	int keyi = begin;
	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}

		Swap(&a[left], &a[right]);
	}

	Swap(&a[left], &a[keyi]);
	keyi = left;
	QuickSortMid(a,begin,keyi-1);
	QuickSortMid(a, keyi + 1, end);
}
3.2.3.快速排序hoare版本改进版小区间优化法
Sort.h

//2.快速排序hoare改进版小区间优化法
void QuickSortSmall(int* a, int begin, int end);

Sort.c

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//三数取中
int GetMidi(int* a, int begin, int end)
{
	int midi = (begin + end) / 2;
	if (a[begin] < a[midi])
	{
		if (a[end] > a[midi])
			return midi;
		else if (a[end] < a[midi])
			return a[begin] > a[end] ? begin : end;

	}
	else if (a[begin] > a[midi])
	{
		if (a[end] < a[midi])
			return midi;
		else if (a[end] > a[midi])
			return a[begin] < a[end] ? begin : end;
	}
	return midi;

}
//2.快速排序hoare版本改进版小区间优化法
void QuickSortSmall(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	//递归到小的子区间时，可以考虑使用插入排序
	//小区间可以随意取，一般取为10
	if (end - begin + 1 <= 10)
	{
		InsertSort(a + begin, end - begin + 1);
	}
	else
	{
		int midi = GetMidi(a, begin, end);
		Swap(&a[midi], &a[begin]);

		int left = begin, right = end;
		int keyi = begin;

		while (left < right)
		{
			// 右边找小
			while (left < right && a[right] >= a[keyi])
			{
				--right;
			}

			// 左边找大
			while (left < right && a[left] <= a[keyi])
			{
				++left;
			}

			Swap(&a[left], &a[right]);
		}

		Swap(&a[left], &a[keyi]);
		keyi = left;

		// [begin, keyi-1] keyi [keyi+1, end]
		QuickSortSmall(a, begin, keyi - 1);
		QuickSortSmall(a, keyi + 1, end);
	}
}
3.2.4.快速排序挖坑法
Sort.h

//快速排序挖坑法
void QuickSort1(int* a, int begin, int end);

Sort.c

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//三数取中
int GetMidi(int* a, int begin, int end)
{
	int midi = (begin + end) / 2;
	if (a[begin] < a[midi])
	{
		if (a[end] > a[midi])
			return midi;
		else if (a[end] < a[midi])
			return a[begin] > a[end] ? begin : end;

	}
	else if (a[begin] > a[midi])
	{
		if (a[end] < a[midi])
			return midi;
		else if (a[end] > a[midi])
			return a[begin] < a[end] ? begin : end;
	}
	return midi;

}
//挖坑法
int PartSort1(int* a, int begin, int end)
{
	int midi = GetMidi(a, begin, end);
	Swap(&a[midi], &a[begin]);

	int key = a[begin];
	int hole = begin;
	while (begin < end)
	{
		//右边找小，填到左边坑
		while (begin < end && a[end] >= key)
		{
			end--;
		}
		a[hole] = a[end];
		hole = end;

		while (begin < end && a[begin] <= key)
		{
			begin++;
		}
		a[hole] = a[begin];
		hole = begin;
	}

	a[hole] = key;
	return hole;
}
//快速排序挖坑版
void QuickSort1(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	int keyi = PartSort1(a, begin, end);
	QuickSort1(a, begin, keyi - 1);
	QuickSort1(a, keyi + 1, end);
}
3.2.5.快速排序双指针法
Sort.h

//快速排序双指针法
void QuickSort2(int* a, int begin, int end);

Sort.c

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//三数取中
int GetMidi(int* a, int begin, int end)
{
	int midi = (begin + end) / 2;
	if (a[begin] < a[midi])
	{
		if (a[end] > a[midi])
			return midi;
		else if (a[end] < a[midi])
			return a[begin] > a[end] ? begin : end;

	}
	else if (a[begin] > a[midi])
	{
		if (a[end] < a[midi])
			return midi;
		else if (a[end] > a[midi])
			return a[begin] < a[end] ? begin : end;
	}
	return midi;

}
//双指针法
int PartSort2(int* a, int begin, int end)
{
	int midi = GetMidi(a, begin, end);
	Swap(&a[midi], &a[begin]);

	int key = begin;
	int prev = begin;
	int cur = prev + 1;

	while (cur <= end)
	{
		if (a[cur] < a[key] && ++prev != cur)
			Swap(&a[cur], &a[prev]);

		cur++;
	}
	Swap(&a[key], &a[prev]);
	key = prev;
	return key;
}
//快速排序双指针版
void QuickSort2(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	int keyi = PartSort2(a, begin, end);
	QuickSort2(a, begin, keyi - 1);
	QuickSort2(a, keyi + 1, end);
}
3.2.6.快速排序非递归版
Strck.h

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>


typedef int STDataType;
typedef struct Strck
{
	STDataType* a;
	int top; 
	int capacity;
}ST;



//初始化/销毁
void STInit(ST* pst);
void STDestroy(ST* pst);

//压栈/出栈
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
//获取栈顶元素
STDataType STTop(ST* pst);

//判空
bool STEmpty(ST* pst);
//统计栈内元素个数
int STSize(ST* pst);

Strck.c

#include"Strck.h"


//初始化/销毁
void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->top = pst->capacity = 0;
}
void STDestroy(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;

}

//压栈/出栈
void STPush(ST* pst, STDataType x)
{
	assert(pst);
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = newcapacity;
	}

	pst->a[pst->top] = x;
	pst->top++;
}
void STPop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	pst->top--;
}
//获取栈顶元素
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);

	return pst->a[pst->top - 1];
}

//判空
bool STEmpty(ST* pst)
{
	assert(pst);

	return pst->top == 0;
}
//统计栈内元素个数
int STSize(ST* pst)
{
	assert(pst);
	return pst->top;
}

Sort.h

//快速排序非递归版
void QuickSortNonR(int* a, int begin, int end);

Sort.c

//快速排序非递归版
void QuickSortNonR(int* a, int begin, int end)
{
	ST s;
	STInit(&s);
	STPush(&s, end);
	STPush(&s, begin);

	while (!STEmpty(&s))
	{
		int left = STTop(&s);
		STPop(&s);
		int right = STTop(&s);
		STPop(&s);

		int keyi = PartSort2(a, left, right);
		//[left,keyi-1] keyi [keyi+1,right]
		if (left < keyi - 1)
		{
			STPush(&s, keyi - 1);
			STPush(&s, left);
		}

		if (keyi + 1 < right)
		{
			STPush(&s, right);
			STPush(&s, keyi + 1);
		}
	}

	STDestroy(&s);
}

3.3.算法完整源码分享

3.3.1函数定义
Strck.h

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>


typedef int STDataType;
typedef struct Strck
{
	STDataType* a;
	int top; 
	int capacity;
}ST;



//初始化/销毁
void STInit(ST* pst);
void STDestroy(ST* pst);

//压栈/出栈
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
//获取栈顶元素
STDataType STTop(ST* pst);

//判空
bool STEmpty(ST* pst);
//统计栈内元素个数
int STSize(ST* pst);

Strck.c

#include"Strck.h"


//初始化/销毁
void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->top = pst->capacity = 0;
}
void STDestroy(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;

}

//压栈/出栈
void STPush(ST* pst, STDataType x)
{
	assert(pst);
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = newcapacity;
	}

	pst->a[pst->top] = x;
	pst->top++;
}
void STPop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	pst->top--;
}
//获取栈顶元素
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);

	return pst->a[pst->top - 1];
}

//判空
bool STEmpty(ST* pst)
{
	assert(pst);

	return pst->top == 0;
}
//统计栈内元素个数
int STSize(ST* pst)
{
	assert(pst);
	return pst->top;
}

Sort.h

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<string.h>
#include<time.h>


//快速排序hoare版本
void QuickSortHoare(int* a, int begin, int end);
//1.快速排序hoare改进版三数取中选key法
void QuickSortMid(int* a, int begin, int end);
//2.快速排序hoare改进版小区间优化法
void QuickSortSmall(int* a, int begin, int end);
//快速排序挖坑法
void QuickSort1(int* a, int begin, int end);
//快速排序双指针法
void QuickSort2(int* a, int begin, int end);
//快速排序非递归版
void QuickSortNonR(int* a, int begin, int end);
3.3.2.算法接口实现
Sort.c

#include"Sort.h"
#include"Strck.h"

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//快速排序hoare版本
void QuickSortHoare(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	int left = begin, right = end;
	int keyi = begin;
	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}

		Swap(&a[left], &a[right]);
	}

	Swap(&a[left], &a[keyi]);
	keyi = left;

	QuickSortHoare(a, begin, keyi - 1);
	QuickSortHoare(a, keyi + 1, end);
}
//三数取中
int GetMidi(int* a, int begin, int end)
{
	int midi = (begin + end) / 2;
	if (a[begin] < a[midi])
	{
		if (a[end] > a[midi])
			return midi;
		else if (a[end] < a[midi])
			return a[begin] > a[end] ? begin : end;

	}
	else if (a[begin] > a[midi])
	{
		if (a[end] < a[midi])
			return midi;
		else if (a[end] > a[midi])
			return a[begin] < a[end] ? begin : end;
	}
	return midi;

}

//1.快速排序hoare版本改进版三数取中选key法
void QuickSortMid(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	int midi = GetMidi(a, begin, end);
	Swap(&a[midi], &a[begin]);

	int left = begin, right = end;
	int keyi = begin;
	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}

		Swap(&a[left], &a[right]);
	}

	Swap(&a[left], &a[keyi]);
	keyi = left;
	QuickSortMid(a,begin,keyi-1);
	QuickSortMid(a, keyi + 1, end);
}
//2.快速排序hoare版本改进版小区间优化法
void QuickSortSmall(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	//递归到小的子区间时，可以考虑使用插入排序
	//小区间可以随意取，一般取为10
	if (end - begin + 1 <= 10)
	{
		InsertSort(a + begin, end - begin + 1);
	}
	else
	{
		int midi = GetMidi(a, begin, end);
		Swap(&a[midi], &a[begin]);

		int left = begin, right = end;
		int keyi = begin;

		while (left < right)
		{
			// 右边找小
			while (left < right && a[right] >= a[keyi])
			{
				--right;
			}

			// 左边找大
			while (left < right && a[left] <= a[keyi])
			{
				++left;
			}

			Swap(&a[left], &a[right]);
		}

		Swap(&a[left], &a[keyi]);
		keyi = left;

		// [begin, keyi-1] keyi [keyi+1, end]
		QuickSortSmall(a, begin, keyi - 1);
		QuickSortSmall(a, keyi + 1, end);
	}
}

//挖坑法
int PartSort1(int* a, int begin, int end)
{
	int midi = GetMidi(a, begin, end);
	Swap(&a[midi], &a[begin]);

	int key = a[begin];
	int hole = begin;
	while (begin < end)
	{
		//右边找小，填到左边坑
		while (begin < end && a[end] >= key)
		{
			end--;
		}
		a[hole] = a[end];
		hole = end;

		while (begin < end && a[begin] <= key)
		{
			begin++;
		}
		a[hole] = a[begin];
		hole = begin;
	}

	a[hole] = key;
	return hole;
}
//快速排序挖坑版
void QuickSort1(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	int keyi = PartSort1(a, begin, end);
	QuickSort1(a, begin, keyi - 1);
	QuickSort1(a, keyi + 1, end);
}
//双指针法
int PartSort2(int* a, int begin, int end)
{
	int midi = GetMidi(a, begin, end);
	Swap(&a[midi], &a[begin]);

	int key = begin;
	int prev = begin;
	int cur = prev + 1;

	while (cur <= end)
	{
		if (a[cur] < a[key] && ++prev != cur)
			Swap(&a[cur], &a[prev]);

		cur++;
	}
	Swap(&a[key], &a[prev]);
	key = prev;
	return key;
}
//快速排序双指针版
void QuickSort2(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	int keyi = PartSort2(a, begin, end);
	QuickSort2(a, begin, keyi - 1);
	QuickSort2(a, keyi + 1, end);
}
//快速排序非递归版
void QuickSortNonR(int* a, int begin, int end)
{
	ST s;
	STInit(&s);
	STPush(&s, end);
	STPush(&s, begin);

	while (!STEmpty(&s))
	{
		int left = STTop(&s);
		STPop(&s);
		int right = STTop(&s);
		STPop(&s);

		int keyi = PartSort2(a, left, right);
		//[left,keyi-1] keyi [keyi+1,right]
		if (left < keyi - 1)
		{
			STPush(&s, keyi - 1);
			STPush(&s, left);
		}

		if (keyi + 1 < right)
		{
			STPush(&s, right);
			STPush(&s, keyi + 1);
		}
	}

	STDestroy(&s);
}
3.3.3.测试代码实现
test.c

#include"Sort.h"

void TestQuickSortHoare()
{
	int a[] = { 2,4,5,7,8,0,9,6,3,1 };
	printf("排序前：");
	PrintArray(a, sizeof(a) / sizeof(int));
	printf("快速排序hoaer版：");
	QuickSortHoare(a, 0,sizeof(a) / sizeof(int)-1);
	PrintArray(a, sizeof(a) / sizeof(int));
	printf("\n");
}
void TestQuickSortMid()
{
	int a[] = { 2,4,5,7,8,0,9,6,3,1 };
	printf("排序前：");
	PrintArray(a, sizeof(a) / sizeof(int));
	printf("快速排序hoare改进版三数取中选key法：");
	QuickSortMid(a, 0, sizeof(a) / sizeof(int) - 1);
	PrintArray(a, sizeof(a) / sizeof(int));
	printf("\n");
}
void TestQuickSortSmall()
{
	int a[] = { 2,4,5,7,8,0,9,6,3,1 };
	printf("排序前：");
	PrintArray(a, sizeof(a) / sizeof(int));
	printf("快速排序hoare改进版小区间优化法：");
	QuickSortSmall(a, 0, sizeof(a) / sizeof(int) - 1);
	PrintArray(a, sizeof(a) / sizeof(int));
	printf("\n");
}
void TestQuickSort1()
{
	int a[] = { 2,4,5,7,8,0,9,6,3,1 };
	printf("排序前：");
	PrintArray(a, sizeof(a) / sizeof(int));
	printf("快速排序挖坑版：");
	QuickSort1(a, 0, sizeof(a) / sizeof(int) - 1);
	PrintArray(a, sizeof(a) / sizeof(int));
	printf("\n");
}
void TestQuickSort2()
{
	int a[] = { 2,4,5,7,8,0,9,6,3,1 };
	printf("排序前：");
	PrintArray(a, sizeof(a) / sizeof(int));
	printf("快速排序双指针版：");
	QuickSort2(a, 0, sizeof(a) / sizeof(int) - 1);
	PrintArray(a, sizeof(a) / sizeof(int));
	printf("\n");
}
void TestQuickSortNonR()
{
	int a[] = { 2,4,5,7,8,0,9,6,3,1 };
	printf("排序前：");
	PrintArray(a, sizeof(a) / sizeof(int));
	printf("快速排序非递归版：");
	QuickSortNonR(a, 0, sizeof(a) / sizeof(int) - 1);
	PrintArray(a, sizeof(a) / sizeof(int));
	printf("\n");
}

int main()
{
   TestQuickSortHoare();
   TestQuickSortMid();
   TestQuickSortSmall();
   TestQuickSort1();
   TestQuickSort2();
   TestQuickSortNonR();

   return 0;
}
3.3.4.测试展示

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/234093.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

基于OpenCV的流水线包装箱检测计数应用(附源码)

基于OpenCV的流水线包装箱检测计数应用(附源码)

导 读 本文主要介绍基于OpenCV的流水线包装箱检测计数应用，并给出源码。 资源下载 完整代码和视频下载地址： https://github.com/freedomwebtech/rpi4-conveyor-belt-boxces-counter 核心代码如下(cboxtest.py): import cv2import numpy as npfrom tracker import*cap=c…
阅读更多...
class067 二维动态规划【算法】

class067 二维动态规划【算法】

class067 二维动态规划 code1 64. 最小路径和 // 最小路径和 // 给定一个包含非负整数的 m x n 网格 grid // 请找出一条从左上角到右下角的路径&#xff0c;使得路径上的数字总和为最小。 // 说明&#xff1a;每次只能向下或者向右移动一步。 // 测试链接 : https://leetcode…
阅读更多...
Fortran读取netcdf文件/WRF中的文件读取

Fortran读取netcdf文件/WRF中的文件读取

一直很好奇WRF到底如何通过netcdf库读取netcdf文件&#xff0c;正巧有个机会&#xff0c;试了下fortran读取nc文件&#xff0c;总结一下。 netcdf库 Fortran读取nc文件需要依赖netcdf外部库。安装该库以后&#xff0c;会有专门写给ffortran函数声明的头文件&#xff1a;netcd…
阅读更多...
RC522（RFID射频模块）读卡ID的简单应用

RC522（RFID射频模块）读卡ID的简单应用

文章目录 一、RFID是什么&#xff1f;二、RC522模块三、使用步骤1.硬件1.硬件连接2.引脚定义 2.软件1.初始化配置代码如下&#xff08;示例&#xff09;&#xff1a;2.引脚配置代码如下&#xff08;示例&#xff09;&#xff1a;3.模块复位代码如下&#xff08;示例&#xff09…
阅读更多...
【工具】JS｜浏览器脚本6分钟极速入门 · 开发一个限制自己刷b站的脚本

【工具】JS｜浏览器脚本6分钟极速入门 · 开发一个限制自己刷b站的脚本

这张图花里胡哨的是让AI生成的&#xff0c;我觉得怪可爱的&#xff0c;就直接作为封面了。 这篇文章中会开发一个JS脚本&#xff0c;这是一个用来限制b站网页版功能的脚本&#xff0c;避免刷b站的时间过长。功能如下&#xff1a; 除了搜索、视频页、私信页之外的任何页都会被重…
阅读更多...
Vue3：修改下拉框el-select的样式

Vue3：修改下拉框el-select的样式

问题 在Vue3项目中&#xff0c;使用了elemen-plus的下拉框&#xff0c;但是使用深度修改下拉框的样式&#xff08;比如下拉框的背景颜色&#xff09;一直不生效 解决 给下拉框框添加 popper-class属性&#xff0c;属性名根据需求取&#xff0c;比如这里取的是"selectSt…
阅读更多...
【Docker】进阶之路：（一）容器技术发展史

【Docker】进阶之路：（一）容器技术发展史

【Docker】进阶之路&#xff1a;&#xff08;一&#xff09;容器技术发展史 什么是容器为什么需要容器容器技术的发展历程Docker容器是如何工作的 什么是容器 容器作为一种先进的虚拟化技术&#xff0c;已然成为了云原生时代软件开发和运维的标准基础设施。在了解容器技术之前…
阅读更多...
【LeetCode刷题】-- 137.只出现一次的数字II

【LeetCode刷题】-- 137.只出现一次的数字II

137.只出现一次的数字II class Solution {public int singleNumber(int[] nums) {Map<Integer,Integer> map new HashMap<>();for(int num : nums){Integer count map.get(num);if(count null){count 1;}else{count;}map.put(num,count);}for(Integer val:map.…
阅读更多...
2023年安全员-B证证考试题库及安全员-B证试题解析

2023年安全员-B证证考试题库及安全员-B证试题解析

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 2023年安全员-B证证考试题库及安全员-B证试题解析是安全生产模拟考试一点通结合&#xff08;安监局&#xff09;特种作业人员操作证考试大纲和&#xff08;质检局&#xff09;特种设备作业人员上岗证考试大纲随机出的…
阅读更多...
LeetCode---374周赛

LeetCode---374周赛

题目列表 2951. 找出峰值 2952. 需要添加的硬币的最小数量 2953. 统计完全子字符串 2954. 统计感冒序列的数目 一、找到峰值 这个简单的模拟&#xff0c;代码如下 class Solution { public:vector<int> findPeaks(vector<int>& mountain) {int nmountain…
阅读更多...
【附源码】完整版，Python+Selenium+Pytest+POM自动化测试框架封装

【附源码】完整版，Python+Selenium+Pytest+POM自动化测试框架封装

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 1、测试框架简介 …
阅读更多...
[每周一更]-(第76期)：Go源码阅读与分析的方式

[每周一更]-(第76期)：Go源码阅读与分析的方式

读源码可以深层理解Go的编写方式&#xff0c;理解作者们的思维方式&#xff1b;也有助于对Go语法用法深刻的理解&#xff0c;我们从这一篇说一下如何读源码&#xff0c;从哪些源码着手&#xff0c;从 简单到深入的方式学习源码&#xff1b; 学习源码也是一个修炼过程&#xff0…
阅读更多...
科技改变旅游，道观漫游可视化：智能化管理助力道观游览

科技改变旅游，道观漫游可视化：智能化管理助力道观游览

道观漫游可视化是一种通过技术手段实现道观游览的可视化展示方式&#xff0c;让游客能够更加直观地了解道观的历史、文化和建筑特色。 随着旅游业的不断发展&#xff0c;道观漫游可视化已经成为了旅游行业中的一个重要方向&#xff0c;吸引了越来越多的游客前来体验。 道观漫游…
阅读更多...
Excel 动态拼接表头实现导出

Excel 动态拼接表头实现导出

public class Column {//单元格内容private String content;//字段名称&#xff0c;用户导出表格时反射调用private String fieldName;//这个单元格的集合private List<Column> listTpamscolumn new ArrayList<Column>();int totalRow;int totalCol;int row;//exc…
阅读更多...
vue使用echarts显示中国地图

vue使用echarts显示中国地图

项目引入echarts以后&#xff0c;在页面创建canvas标签 引入一个公共js文件&#xff08;下面这段代码就是china.js文件&#xff09; (function (root, factory) {if (typeof define function && define.amd) {// AMD. Register as an anonymous module.define([ex…
阅读更多...
孜然地址引导页V9(带后台)

孜然地址引导页V9(带后台)

刚刚在浏览之前经常访问的网站的时候我发现他不用那个域名了&#xff0c;然后我见这个页面好看&#xff0c;就把他干下来了&#xff0c;然后把给他写了个后台。另外如果你的子页面收录多的话&#xff0c;人家百度访问你的子页面会显示404的&#xff0c;所以为了流量可观安装这个…
阅读更多...
【带头学C++】----- 九、类和对象 ---- 9.8 动态对象创建

【带头学C++】----- 九、类和对象 ---- 9.8 动态对象创建

目录 9.8 动态对象创建 9.8.1 动态创建对象基础概念 9.8.2 C语言创建动态对象的 9.8.3 new创建动态对象 9.8.4 delete释放动态对象 9.8.5 动态对象数组 9.8 动态对象创建 9.8.1 动态创建对象基础概念 在创建数组时&#xff0c;我们通常需要预先指定数组的长度&#xff0…
阅读更多...
三个臭皮匠（ctr,nerdctl,crictl）顶一个诸葛亮（docker）

三个臭皮匠（ctr,nerdctl,crictl）顶一个诸葛亮（docker）

文章目录 containerd简介 nerdctl简介安装精简 Minimal 安装完整Full 安装启动服务 命令参数容器运行容器列出容器详情容器日志容器进入容器停止容器删除镜像列表镜像拉取镜像标签镜像导出镜像导入镜像删除镜像构建配置tab键配置加速配置仓库http方式https方式 ctr简介命令参数…
阅读更多...
java--Calendar

java--Calendar

1.Calendar ①代表的是系统此刻时间对应的日历 ②通过它可以单独获取、修改时间中的年、月、日、时、分、秒等(月份是从0开始的)。 2.Calender日历类的常见方法 注意&#xff1a;calender是可变对象&#xff0c;一旦修改后其对象本身表示的时间将产生变化。
阅读更多...
8. MySQL 触发器

8. MySQL 触发器

目录 概述 定义 触发器特性&#xff1a; 基础操作 创建触发器 NEW和OLD 其他操作 查看触发器 删除触发器 注意事项 概述 定义 触发器&#xff0c;就是一种特殊的存储过程。触发器和存储过程一样是一个能够完成特定功能、存储在数据库服务器上的SQL片段&#xff0c;但是触…
阅读更多...
最新文章

Copyright @ 2022~2023