前往小程序，Get更优阅读体验！
立即前往
文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
首页
学习
活动
专区
圈层
工具
MCP广场
返回腾讯云官网
社区首页 >专栏 >数据结构：七种排序及总结

数据结构：七种排序及总结

作者头像
用户11290664
发布于 2024-11-21 07:39:48
发布于 2024-11-21 07:39:48
11900
代码可运行
举报
文章被收录于专栏：学习学习
运行总次数：0
代码可运行
关联问题
换一批

排序

我们数据结构常见的排序有四大种，四大种又分为七小种，如图所示

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。 稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次 序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排 序算法是稳定的；否则称为不稳定的。 内部排序：数据元素全部放在内存中的排序。 外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不断地在内外存之间移动数据的排序。

一插入排序

1直接插入排序

void InsertSort(int* a, int n);

从i=0开始遍历，每次i之前的序列都是有序的，通过判断当前i的值能够在i之前哪个位置，找到后直接插入，

为什么直接插入排序最坏的情况是n^2？ 如果一个开始原序列是降序，想排为升序 第一个循环是n，第二个循环最坏是n，所以是最大n^2

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
void InsertSort(int* arr, int n) {


	for (int i = 0; i < n-1; i++) {
		int end = i;

		int tem = arr[end + 1];
		while (end >= 0) {
			

	
			if (arr[end] > tem) {

				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				
		
				break;
			}

		}
		arr[end + 1] = tem;
	
	
	}
	

}

2希尔排序

希尔排序是对直接插入排序的优化，大大优化了时间复杂度 他们是先规定了一个gap值，然后每次进行循环把gap值缩小，最后把 gap值调为1。这样最后一次排序就是直接插入排序，前面的是预排序。 条件就是

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
while(gap>1){
gap=gap/3+1;//最后一次gap=1随后跳出循环


}
代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
void ShellSort(int* arr, int n) {

	int gap = n;
	while(gap>1){
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++) {

			
			int end = i;

			int tem = arr[end +gap];
			while (end >= 0) {



				if (arr[end] > tem) {

					arr[end + gap] = arr[end];
					end-=gap;
				}
				else
				{



					break;
				}

			}
			arr[end + gap] = tem;
		}	
	
	}


}

判断两种排序的时间复杂度

二选择排序

3直接选择排序

直接选择排序就是一种很暴力的解法，思路简单，代码简单，但是时间复杂度很差，和 冒泡排序差不多

思路就是分别从两头找最大和最小，然后对下标进行++ – 然后直到相遇。

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
void SeletSort(int* arr, int n) {
	int end = n - 1;
	int begin = 0;
	int max, min;
	max = min = 0;
	while (begin < end) {
		max = min = begin;
		for (int i = begin + 1; i <= end; i++)
		{
		
			if (arr[i] > arr[max]) {
				max = i;

			}
			if (arr[i] < arr[min])
			{
				min = i;
			}

		}
		if (max == begin) {
			max = min;
		}
		Swap(&arr[min], &arr[begin]);
		Swap(&arr[max], &arr[end]);
		begin++;
		end--;

	}

}

有一种特殊情况要处理就是换的时候max在begin位置，因为先&arr[min], &arr[begin]换，所以要提前max=min.(此时最大值在min下标位置)

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
	if (max == begin) {	max = min;		}

时间复杂度n*(n/2+n/2)=n^2.

4堆排序

要了解堆排序我们要先了解一些误区： 1无论向下调整算案建堆还是向上调整算法建堆都是形成一个二叉树结构，本身并没有让数组完全有序， 2向下调整算法建堆比向上调整算法建堆时间复杂度更优 3排升序建大堆，排降序 建小堆。

所以我们要先完成堆排序的话要完成两个步骤， 1把原序列进行向下或向上调整遍历，成为一个堆的结构， 2因为头结点一定是最值，我们每次把arr[0]和arr[end]交换，再让end–完成之后就完成排序。

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
void HeapSort(HeapType* arr, int n) {//第一步

	for (int i = (n - 1 - 1) / 2; i >= 0; i--) {


		AdjustDown(arr, i, n);

	}
	int end = n - 1;
	for (int i = end; i > 0; i--) {//第二步
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end);
		end--;



	}
}

因为向下调整算法建堆的时间复杂度大概是O（n） 第二部大概是O(nlogn) 故时间复杂度O（n+nlogn）大概是O（n*logn）.

三 交换排序

5冒泡排序

冒泡排序两层循环o(n^2) 加上优化还是最好情况O（n）所以是O（n^2）

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
void BubbleSort(int* a, int n) {
	for (int i = 0; i < n - 1; i++)
	{
		int xz = 0;
		for (int j = 0; j < n - i - 1; j++) {

			
			if (a[j] > a[j + 1]) {

				swap(&a[j], &a[j + 1]);
				xz = 1;
			}

			
		}
		if (xz == 0) {
			break;
		}

	}

}

6快速排序

快排我们用的找中间值 ，然后分区间，类似堆排序，时间复杂度o（nlogn） 按最情况来说，每次循环排最差情况是n/2+n/2=n,一共是logn次循环（最好情况，每次中间值恰好在中间） 按最坏情况是n次循环，所以时间复杂度为nlogn~n^2.

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
int GetKeyi(int* arr, int left, int right) {
	int keyi = left;
	left++;
	while (right>=left)
	{
		while (left<=right&&arr[right]>arr[keyi]) {
			right--;


		}

		while (left <= right && arr[left] < arr[keyi]) {

			left++;

			}
		if (left <= right) {

			swap(&arr[right--], &arr[left++]);
		}
		

	}

	swap(&arr[keyi], &arr[right]);
	return right;
}
void QuickSort(int* arr, int left,int right) {
	if (left >= right) {
		return;
	}
	int keyi = GetKeyi(arr, left, right);
	QuickSort(arr, left,keyi - 1);
	QuickSort(arr, keyi+1,right);

}

四 归并排序

7归并排序

归并排序的思想是通过二分找中间值，[left,中间值] ，[中间值+1,right]两个序列再二分，直到left>=中间值，然后通过递归返回原来的函数栈帧进行排序，因为只有logn个函数栈帧，每次栈帧内最坏排n个数据。

为了不破坏arr序列，我们定义了tem序列接收，然后最后把tem数组覆盖arr, 时间复杂度为n*logn

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
void MergeSort(int* arr, int n) {
	int* tem = (int*)malloc(sizeof(int) * n);
	_MergeSort(arr,0, n - 1,tem);
	free(tem);



}
void _MergeSort(int* arr, int left, int right, int* tem) {
	if (left >= right) {
		return;
	}
	int mid = (left + right) / 2;
	_MergeSort(arr, left, mid, tem);
	_MergeSort(arr, mid+1, right, tem);
	int begin1 = left;
	int begin2 = mid + 1;
	int end1 = mid;
	int end2 = right;
	int x = begin1;
	while (begin1 <= end1 && begin2 <= end2) {

		if (arr[begin1] < arr[begin2]) {	
			tem[x++] = arr[begin1++];
		}
		else
		{
			tem[x++] = arr[begin2++];
		}
	}
	while (begin1 <= end1) {
		tem[x++] = arr[begin1++];
	}
	
	while (begin2 <= end2) {
		tem[x++] = arr[begin2++];
	}
	for (int i = left; i < right; i++)
	{
		arr[i] = tem[i];
	}
}

最后总结一下所有排序时间

源码

Sort.h

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<assert.h>
#include<stdbool.h>
typedef int HeapType;
typedef struct Heap {

	HeapType* a;
	int capacity;
	int size;

}Heap;
void SeletSort(HeapType* arr, int n);
void Inite(Heap* p);
void Push(Heap* p, HeapType x);
void Pop(Heap* p);
bool Empty(Heap* p);
HeapType Top(Heap* p);
void Print(Heap* p);
void Destry(Heap* p);
void Swap(HeapType* a, HeapType* b);
void AdjustUp(HeapType* a, int child);
void AdjustDown(HeapType* a, int parent, int n);
void HeapSort(HeapType* arr, int n);

void BubbleSort(int* a, int n);
void swap(int* a, int* b);
void InsertSort(int* arr, int n);
void ShellSort(int* arr, int n);
int GetKeyi(int* arr, int left, int right);
void QuickSort(int* arr, int left, int right);
void MergeSort(int* arr,int n);
void _MergeSort(int* arr, int left, int right, int* tem);

void test();

test.c

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
#define  _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"
#include"time.h"
#include"stdlib.h"

int main() {
	test();




	return 0;
}

Sort.c

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
#define  _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"


void test() {
	srand((unsigned)time(0));
	const int N = 100000;
	int* a1 = (int*)malloc(sizeof(int) * N);//创建100000个空间的数组

	int* a2 = (int*)malloc(sizeof(int) * N);//创建100000个空间的数组
	int* a3 = (int*)malloc(sizeof(int) * N);//创建100000个空间的数组

	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();//循环100000次，每次赋予a1数组随机值

		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();
	SeletSort(a3, N);
	int end3 = clock();
	int begin4 = clock();
	HeapSort(a4, N);
	int end4 = clock();
	int begin5 = clock();
	BubbleSort(a5, N);
	int end5 = clock();
	int begin6= clock();
	QuickSort(a6, 0,N-1);
	int end6 = clock();
	int begin7 = clock();
	MergeSort(a7,  N - 1);
	int end7 = 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("BubbleSort:%d\n", end5 - begin5);
	printf("QuickSort:%d\n", end6 - begin6);
	printf("MergeSort:%d\n", end7 - begin7);






}
void swap(int* a, int* b) {
	int tmp = *a;

	*a = *b;
	*b = tmp;



}
void BubbleSort(int* a, int n) {
	for (int i = 0; i < n - 1; i++)
	{
		int xz = 0;
		for (int j = 0; j < n - i - 1; j++) {

			
			if (a[j] > a[j + 1]) {

				swap(&a[j], &a[j + 1]);
				xz = 1;
			}

			
		}
		if (xz == 0) {
			break;
		}

	}

}

void InsertSort(int* arr, int n) {


	for (int i = 0; i < n - 1; i++) {
		int end = i;

		int tem = arr[end + 1];
		while (end >= 0) {



			if (arr[end] > tem) {

				arr[end + 1] = arr[end];
				end--;
			}
			else
			{


				break;
			}

		}
		arr[end + 1] = tem;


	}


}
void ShellSort(int* arr, int n) {

	int gap = n;
	while (gap > 1) {
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++) {


			int end = i;

			int tem = arr[end + gap];
			while (end >= 0) {



				if (arr[end] > tem) {

					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{



					break;
				}

			}
			arr[end + gap] = tem;
		}

	}


}
void SeletSort(int* arr, int n) {
	int end = n - 1;
	int begin = 0;
	int max, min;
	max = min = 0;
	while (begin < end) {
		max = min = begin;
		for (int i = begin + 1; i <= end; i++)
		{

			if (arr[i] > arr[max]) {
				max = i;

			}
			if (arr[i] < arr[min])
			{
				min = i;
			}

		}
		if (max == begin) {
			max = min;
		}
		Swap(&arr[min], &arr[begin]);
		Swap(&arr[max], &arr[end]);
		begin++;
		end--;

	}

}
void Inite(Heap* p) {
	p->a = NULL;
	p->capacity = p->size = 0;



}
void Push(Heap* php, HeapType x)
{
	assert(php);

	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HeapType* tmp = (HeapType*)realloc(php->a, newcapacity * sizeof(HeapType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		php->a = tmp;
		php->capacity = newcapacity;
	}

	php->a[php->size] = x;
	php->size++;

	AdjustUp(php->a, php->size - 1);
}
void Pop(Heap* p) {
	Swap(&p->a[0], &p->a[p->size - 1]);



	p->size--;
	AdjustDown(p->a, 0, p->size);


}
bool Empty(Heap* p) {
	return p->size == 0;


}
HeapType Top(Heap* p) {

	return p->a[0];

}
void Print(Heap* p) {
	{
		while (!Empty(p))
		{
			printf("%d ", Top(p));
			Pop(p);
		}

	}
}
void Swap(HeapType* a, HeapType* b) {

	int tem = *a;
	*a = *b;
	*b = tem;

}
void AdjustUp(HeapType* a, int child) {


	int parent = (child - 1) / 2;
	while (child > 0) {
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;

		}

		else
		{
			break;
		}

	}

}



void AdjustDown(HeapType* a, int parent, int n) {
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child] > a[child + 1]) {
			child = child + 1;


		}
		if (a[parent] > a[child]) {
			Swap(&a[parent], &a[child]);
			parent = child;
			child = child * 2 + 1;
		}
		else
		{
			break;
		}

	}

}
void HeapSort(HeapType* arr, int n) {

	for (int i = (n - 1 - 1) / 2; i >= 0; i--) {


		AdjustDown(arr, i, n);

	}
	int end = n - 1;
	for (int i = end; i > 0; i--) {
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end);
		end--;



	}
}
int GetKeyi(int* arr, int left, int right) {
	int keyi = left;
	left++;
	while (right>=left)
	{
		while (left<=right&&arr[right]>arr[keyi]) {
			right--;


		}

		while (left <= right && arr[left] < arr[keyi]) {

			left++;

			}
		if (left <= right) {

			swap(&arr[right--], &arr[left++]);
		}
		

	}

	swap(&arr[keyi], &arr[right]);
	return right;
}
void QuickSort(int* arr, int left,int right) {
	if (left >= right) {
		return;
	}
	int keyi = GetKeyi(arr, left, right);
	QuickSort(arr, left,keyi - 1);
	QuickSort(arr, keyi+1,right);

}
void MergeSort(int* arr, int n) {
	int* tem = (int*)malloc(sizeof(int) * n);
	_MergeSort(arr,0, n - 1,tem);
	free(tem);



}
void _MergeSort(int* arr, int left, int right, int* tem) {
	if (left >= right) {
		return;
	}
	int mid = (left + right) / 2;
	_MergeSort(arr, left, mid, tem);
	_MergeSort(arr, mid+1, right, tem);
	int begin1 = left;
	int begin2 = mid + 1;
	int end1 = mid;
	int end2 = right;
	int x = begin1;
	while (begin1 <= end1 && begin2 <= end2) {

		if (arr[begin1] < arr[begin2]) {	
			tem[x++] = arr[begin1++];
		}
		else
		{
			tem[x++] = arr[begin2++];
		}
	}
	while (begin1 <= end1) {
		tem[x++] = arr[begin1++];
	}
	
	while (begin2 <= end2) {
		tem[x++] = arr[begin2++];
	}
	for (int i = left; i < right; i++)
	{
		arr[i] = tem[i];
	}
}
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-11-07，如有侵权请联系 cloudcommunity@tencent.com 删除
数组
数据结构
int
void
排序

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

数组
数据结构
int
void
排序
评论
登录后参与评论
暂无评论
登录 后参与评论
推荐阅读
ConardLi0
LV.1
这个人很懒，什么都没有留下～
文章
581
获赞
1.4K
专栏
1
目录
  • 排序
  • 一插入排序
  • 1直接插入排序
  • 2希尔排序
  • 二选择排序
  • 3直接选择排序
  • 4堆排序
  • 三 交换排序
  • 5冒泡排序
  • 6快速排序
  • 四 归并排序
  • 7归并排序
  • 源码
加入讨论
的问答专区 >
王新栋0
相关课程
一站式学习中心 >
AI代码助手快速上手训练营
1852人在学
腾讯云代码助手
区块链
290人在学
区块链
低代码实战营
266人在学
微搭低代码
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号 | 京公网安备号11010802020287

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2025 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论
1