IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 常见排序算法 -> 正文阅读

[数据结构与算法]常见排序算法

几个基础概念:

稳定:如果原数组中a在b的前面a与b相等,且排序之后a仍然在b的前面,称为该算法稳定。否则为不稳定。

排序算法中经常用到排序的起始位置数组长度以及交换操作

注意:有些传入函数的参数是数组和数组长度,而有一些是数组和左下标及右下标。

//起始位置
int start = 0;
//数组长度
int length = sizeof(arr)/sizeof(int);

//交换两个数值的函数
void swap(int &a,int &b){
	int temp = a;
	a = b;
	b = temp;
}

1.冒泡排序bubble sort

通过对待排序序列从前到后(从下标较小的元素开始),依次比较相邻元素的值,若发现逆序则交换,使值较大的元素之间从前部移到后部。前后两个指针,每一轮确定当前的最大值位置。

逆序交换

时间复杂度:O(n^2)。

空间复杂度:O(1)。

是否稳定:稳定。

void bubble_sort(int arr[],int length){
	for(int i = 0;i<length;i++){
		for(int j = 0;j < length;j++){
			if(q[i] > q[j]) swap(q[i],q[j]);
		}
	}
}

调用方法:

bubble_sort(arr, length);

2.选择排序selection sort

第一次找出arr[0,n-1]中确定最小值和arr[0]交换,第二次找出arr[1,n-1]中确定最小值和arr[1]交换......

最小值交换

时间复杂度:O(n^2)

空间复杂度:O(1)

是否稳定:不稳定

void selection_sort(int arr[],int length) {
	int min ;
	//事实上遍历length-1次也是可以的
	for (int i = 0; i < length ; i++) {
		//每次找到从i+1到length的最小值
        min = i;
		for (int j = i + 1; j < length; j++) {
			if (arr[min] > arr[j]) min = j;
		}
		swap(arr[min], arr[i]);
	} 
}

3.快速排序

快速排序先找到一个基准值,使得数组分为两部分:左边都是小于该基准值的数,右边都是大于该基准值的数。然后对左右两部分再以同样的方法排序。

时间复杂度:O(nlogn)

空间复杂度:O(1)

是否稳定:不稳定

void quick_sort(int arr[], int left, int right) {
	if (left >= right)return;
	int i = left - 1, j = right + 1;
    //以中间点作为基准值
	int x = arr[(left + right) / 2];
	while (i < j) {
		do i++; while (arr[i] < x);
		do j--; while (arr[j] > x);
        //左边大于x的数和右边小于x的数交换
		if (i < j)swap(arr[i], arr[j]);
	}
    //分别对左右两边以同样的方法排序,注意边界
	quick_sort(arr, left, j);
	quick_sort(arr, j + 1, right);
}

调用方法:注意这里的 left 和 right 是下标,尤其是 right 需要 length-1.

quick_sort(arr,start,length-1)

4.归并排序merge sort

归并排序基于分治思想,首先确定分界点,然后递归排序左边和右边,最后再把两个部分合并起来。归并排序需要一个中间数组。

时间复杂度:O(nlogn)

空间复杂度:O(n)

是否稳定:稳定

//额外数组
int temp[N];
void merge_sort(int arr[], int left, int right) {
	if (left >= right)return;
	//确定分界点
	int mid = (left + right) / 2;
	//递归排序left right
	merge_sort(arr, left, mid), merge_sort(arr, mid + 1, right);
	//归并合二为一
	int k = 0, i = left, j = mid + 1;
	while (i <= mid && j <= right) {
		if (arr[i] < arr[j])temp[k++] = arr[i++];
		else temp[k++] = arr[j++];
	}
	while (i <= mid)temp[k++] = arr[i++];
	while (j <= right)temp[k++] = arr[j++];
	//复制回去
	for (i = left, j = 0; i <= right; i++, j++) {
		arr[i] = temp[j];
	}

}

调用方法:

merge_sort(arr,start,length-1);

5.插入排序insertion sort

插入排序类似于扑克牌的整理,先把下标为0的数看成是有序的,从下标为1的数开始与前一个数相比较。只要比前面的数值小就要往前排。

时间复杂度:O(n^2)

空间复杂度:O(1)

是否稳定:稳定

void insertion_sort(int arr[], int length) {
	for (int i = 0; i < length ; i++) {
		for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
			swap(arr[j], arr[j - 1]);
		}
	}
}
void insertion_sort2(int arr[], int length) {

	for (int i = 1; i < length; i++) {
		//先保存要插入的数
		int insertVal = arr[i];
		int insertIdx = i-1;
		//只要不越界并且满足要插入的数小于前面的数
		while (insertIdx>=0&&insertVal<arr[insertIdx]) {
			arr[insertIdx++] = insertVal;
			insertIdx--;
		}
		//当退出循环时说明插入的位置是insertIdx+1
		arr[insertIdx + 1] = insertVal;
	}
}

6.堆排序heap sort

先把数组构造成一个大顶堆(父节点大于子节点),然后把堆顶(数组最大值,数组第一个元素)和数组最后一个元素交换,这样就把最大值放到了数组最后边。把数组长度减一,在进行构造堆。

时间复杂度:O(nlogn)

空间复杂度:O(1)

是否稳定:不稳定

void adjust_heap(int a[], int x, int n)
{
    //x是待调整结点的下标,n是待调整的最后一个元素的下标
	int l = x * 2 + 1;//左子结点的下标
	int r = x * 2 + 2;//右子结点的下标
	int max = x;

	if (l < n && a[l] > a[max]) max = l;
	if (r < n && a[r] > a[max]) max = r;

	if (max != x)
	{
		swap(a[x], a[max]);
		adjust_heap(a, max, n);
	}
}

void heap_sort(int arr[], int length)
{
	for (int i = length / 2 - 1; i >= 0; i--)
		adjust_heap(arr, i, length); //建初始堆

    //进行n-1次排序
	for (int i = length - 1; i > 0; i--)
	{
		swap(arr[0], arr[i]);   //根结点与最后一个元素交换
		adjust_heap(arr, 0, i); //对数组重新建堆
	}
}

7.计数排序

桶思想的一种,是一种非比较排序,将整数按位数切割成不同的数字,然后按每个位数分别比较。适用于整数数字量很大但是数值的范围小且已知的情况下。开辟一个数组,数组的下标作为代表的值,array[ i ]表示在数值 i 有array[ i ]个。

例:某大型企业员工的年龄排序,快速得知高考名次。

时间复杂度:O(n)


void bucket_sort(int arr[], int length) {
	//这里设arr数组的数值范围在[0,100]则需要开辟一个101个值的数组
	//并且初始化为不在数值范围的数
	int count[103] = {0};
	//计数
	for (int i = 0; i < length; i++) count[arr[i]]++;
	//再把临时数组的值赋给原数组
	int count_size = sizeof(count) / sizeof(int);
	for (int i = 0, j = 0; i < count_size; i++) {
		while (count[i]-- > 0)arr[j++] = i;
	}
}

8.希尔排序shell sort

是基于插入排序的一种更高效的排序方法,也称为缩小增量排序。

希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序。随着增量逐渐减少,每组包含的关键词越来越多,当增量减到1整个数组正好分成一组,算法终止。

时间复杂度:

空间复杂度:

是否稳定:

①基于交换的希尔排序:找到一个就交换一个。


void shell_sort1(int arr[], int length) {
	int temp = 0;
	//每次一组的大小为一半
	for (int gap = length / 2; gap > 0; gap /= 2) {
		//下标i和下标j的数分别表示对比的两组
		//遍历各组中所有元素(共gap组,每组为length/gap个数据)步长gap
		for (int i = gap; i < length; i++) {
			for (int j = i - gap; j >= 0; j -= gap) {
				//如果当前元素大于加上步长后的那个元素,交换
				if (arr[j] > arr[j + gap])swap(arr[j], arr[j + gap]);
			}
		}
	}
}

②基于移位的希尔排序(更快)

void shell_sort2(int arr[],int length) {

	//增量每次都/2
	for (int step = length / 2; step > 0; step /= 2) {

		//从增量那组开始进行插入排序,直至完毕
		for (int i = step; i < length; i++) {

			int j = i;
			int temp = arr[j];
			//arr[j]和arr[j-step]是要移动的一组数
			while (j - step >= 0 && arr[j - step] > temp) {
				arr[j] = arr[j - step];
				j = j - step;
			}
			//循环结束则找到那个temp的位置。
			arr[j] = temp;
		}
	}
}

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-07-27 16:29:50  更:2021-07-27 16:30:48 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/25 17:29:33-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码