1. Toy模板网首页
  2. > Toy博客

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

10月前 作者：圥忈ゼ 分类：Toy博客 阅读(44) 违法举报

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

一.交换排序

1.基本思想

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

2.冒泡排序

2.1.算法讲解

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

【数据结构 — 排序 — 交换排序】,# 数据结构,## 排序,C语言,数据结构,排序算法,算法,c语言

冒泡排序的特性总结：

  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.测试展示

【数据结构 — 排序 — 交换排序】,# 数据结构,## 排序,C语言,数据结构,排序算法,算法,c语言

3.快速排序

3.1.算法讲解

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

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

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

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

快速排序的特性总结：

  1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
  2. 时间复杂度：O(N*logN)
    【数据结构 — 排序 — 交换排序】,# 数据结构,## 排序,C语言,数据结构,排序算法,算法,c语言
  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.测试展示

【数据结构 — 排序 — 交换排序】,# 数据结构,## 排序,C语言,数据结构,排序算法,算法,c语言文章来源地址https://www.toymoban.com/news/detail-761217.html

到了这里，关于【数据结构 — 排序 — 交换排序】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

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

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

    基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。 2.1.算法讲解 以下只讲解冒泡排序代码的简单实现 ，想要更详细的了解冒泡排序

    2024年02月04日
    浏览(44)
  • 第11章：C语言数据结构与算法初阶之排序

    第11章：C语言数据结构与算法初阶之排序

    排序是一种非常重要的算法。 排序 ：所谓排序，就是使一串记录，按照其中的某个或某些的大小，递增或递减的排列起来的操作。 稳定性 ：假定在待排序的记录序列中，存在多个具有相同的的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，

    2024年02月12日
    浏览(47)
  • 【数据结构】排序之交换排序（冒泡 | 快排）

    【数据结构】排序之交换排序（冒泡 | 快排）

    在之前的博客中介绍了插入排序，有需要的可以点这个链接: link，这次来介绍交换排序，包括冒泡和快排。 话不多说，正文开始。 基本思想 ：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。 交换排序的特点是：将键值较大的记录向序

    2024年02月03日
    浏览(39)
  • 【数据结构】交换排序

    【数据结构】交换排序

    ⭐ 作者：小胡_不糊涂 🌱 作者主页：小胡_不糊涂的个人主页 📀 收录专栏：浅谈数据结构 💖 持续更文，关注博主少走弯路，谢谢大家支持 💖 交换排序基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。 代码实现： 快速排

    2024年02月08日
    浏览(46)
  • 【数据结构】排序（插入、选择、交换、归并） -- 详解

    【数据结构】排序（插入、选择、交换、归并） -- 详解

    1、排序的概念 排序 ：所谓排序，就是使一串记录，按照其中的某个或某些的大小， 递增或递减 的排列起来的操作。 稳定性 ：假定在待排序的记录序列中，存在多个具有相同的的记录，若经过排序，这些记录的 相对次序保持不变 ，即在原序列中，r[i] = r[j]，

    2024年02月11日
    浏览(39)
  • 【数据结构常见七大排序（三）上】—交换排序篇【冒泡排序】And【快速排序】

    【数据结构常见七大排序（三）上】—交换排序篇【冒泡排序】And【快速排序】

    目录 前言 1.冒泡排序 1.1冒泡排序动图 1.2冒泡排序源代码 1.3冒泡排序的特性总结 2.快速排序👑 2.1hoare版本实现思想 排序前 排序中 排序后 2.2hoare版本快排源代码 2.3分析先走 情况1🥇 情况2🥈 交换类排序两个常见的排序算法【冒泡排序】、【快速排序】 交换排序基本思想：

    2024年02月16日
    浏览(70)

  • 数据结构（C语言实现）——常见排序算法的基本思想及实现（快速排序的三种方法和优化及非递归实现快速排序）

    生活中几乎处处都会用到排序，比如：网购时的店铺顺序，学生成绩的排名等，今天我们就来学习数据结构中常见的几种排序算法。 排序 ：所谓排序，就是使一串记录，按照其中的某个或某些的大小，递增或递减的排列起来的操作。 稳定性 ：假定在待排序的记录序列

    2023年04月24日
    浏览(66)
  • 数据结构进阶篇 之 【交换排序】（冒泡排序，快速排序递归、非递归实现）详细讲解

    数据结构进阶篇 之 【交换排序】（冒泡排序，快速排序递归、非递归实现）详细讲解

    当你觉的自己不行时，你就走到斑马线上，这样你就会成为一个行人 1.1 基本思想 1.2 实现原理 1.3 代码实现 1.4 冒泡排序的特性总结 2.1 基本思想 2.2 递归实现 2.2.1 hoare版 2.2.2 前后指针版本 2.3 快速排序优化 2.3.1 随机数选key 2.3.2 三数取中选key 2.3.3 递归到小的子区间使用插入排

    2024年04月10日
    浏览(68)
  • 数据结构：排序- 插入排序(插入排序and希尔排序) , 选择排序(选择排序and堆排序) , 交换排序(冒泡排序and快速排序) , 归并排序

    数据结构：排序- 插入排序(插入排序and希尔排序) , 选择排序(选择排序and堆排序) , 交换排序(冒泡排序and快速排序) , 归并排序

    目录 前言 复杂度总结 预备代码 插入排序 1.直接插入排序: 时间复杂度O(N^2) 空间复杂度O(1) 复杂度（空间/时间）： 2.希尔排序： 时间复杂度 O(N^1.3~ N^2） 空间复杂度为O(1) 复杂度（空间/时间）： 选择排序 1.直接选择排序 时间复杂度O(N^2)/空间复杂度O(1) 复杂度（空间/时间）

    2024年02月07日
    浏览(57)
  • 数据结构——排序算法——归并排序

    数据结构——排序算法——归并排序

    在第二个列表向第一个列表逐个插入的过程中，由于第二个列表已经有序，所以后续插入的元素一定不会在前面插入的元素之前。在逐个插入的过程中，每次插入时，只需要从上次插入的位置开始，继续向后寻找插入位置即可。这样一来，我们最多只需要将两个有序数组遍历

    2024年02月09日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包