1.排序的概念

排序就是使一串数据按照特定的规律比较,进行排列出来的操作。

常见的排序算法

//排序实现的接口 void InsertSort(int* a,int n); //插入排序 void ShellSort(int* a,int n);
//希尔排序 void SelectSort(int* a, int n); // 选择排序 void AdjustDwon(int* a, int n,
int root); void HeapSort(int* a, int n);// 堆排序 // 冒泡排序 void BubbleSort(int* a,
int n) // 快速排序递归实现 // 快速排序hoare版本 int PartSort1(int* a, int left, int right);
// 快速排序挖坑法 int PartSort2(int* a, int left, int right); // 快速排序前后指针法 int
PartSort3(int* a, int left, int right); void QuickSort(int* a, int left, int
right); // 快速排序 非递归实现 void QuickSortNonR(int* a, int left, int right) //
归并排序递归实现 void MergeSort(int* a, int n) // 归并排序非递归实现 void MergeSortNonR(int* a,
int n) // 计数排序 void CountSort(int* a, int n)
2.常见排序的实现

1.插入排序

直接插入

直接插入法是一种简单的插入排序法,是将待排序元素逐个插入到一个已经排序好的有序序列中,形成一个新的有序序列。

就好像将{3,6,1,5}插入到{2,4}中,得到{1,2,3,4,5,6}。

那它是怎么实现的呢?

直接插入的特性

*  1.元素插入前越接近有序,插入的效率越高
* 2.时间复杂度:O(N^2)
* 3.空间复杂度:O(1)
* 4.稳定性:稳定

希尔排序(缩小增量排序)

希尔排序法是先选定一个整数,将待排序元素分为几个组,所有距离相等的分在同一组,并对每一组元素进行排序。

希尔排序的特性

*  1.希尔排序是对直接插入排序的优化
* 2.gap>1时都是预排序,目的是让排序元素更接近有序。
* 3.时间复杂度:O(N^1.3——N^2)
* 4.稳定性:不稳定
2.选择排序

每次从待排序元素中选出最小(最大)的一个,放在序列的起始位置,直到全部元素排完。

直接选择排序

直接选择是将待排序元素相比较,选出最大或最小的一个,然后剩下的元素重复此操作,直至剩下元素为1,停止操作。

直接选择排序的特性

* 1.直接选择排序好理解,但是效率不是很好,实际中很少应用
* 2.时间复杂度:O(N^2)
* 3.空间复杂度:O(1)
* 4.稳定性:不稳定

 堆排序

堆排序是利用堆这种数据结构设计出的一种排序算法,是选择排序的一种。记住排升序建大堆,排降序建小堆。

 堆排序的特点

* 1. 堆排序使用堆来选数,效率就高了很多。
* 2. 时间复杂度:O(N*logN)
* 3. 空间复杂度:O(1)
* 4. 稳定性:不稳定
3.交换排序

根据两个元素的比较结果交换两者的顺序,将较大的值向尾部移动,较小的值向前面移动。

冒泡排序

冒泡排序的特点

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

快速排序

快排是一种二叉树交换排序方法,任取其中某元素作为基准值,然后由此将集合分为两个序列,左小于右,同上重复。

将区间按照基准值划分为左右两半部分的常见方式有:

* 1. hoare版本
* 2. 挖坑法
* 3. 前后指针版本

4.归并排序

归并排序是将已有的子序列排序,将两个有序表合并成一个有序表。

归并排序的特点

* 1. 归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问题。
* 2. 时间复杂度:O(N*logN)
* 3. 空间复杂度:O(N)
* 4. 稳定性:稳定
5.非比较排序

非比较排序的特点

*  1. 计数排序在数据范围集中时,效率很高,但是适用范围及场景有限。
* 2. 时间复杂度:O(MAX(N,范围))
* 3. 空间复杂度:O(范围)
* 4. 稳定性:稳定

技术
©2019-2020 Toolsou All rights reserved,
TypeScript:函数类型接口8道大厂指针笔试题让你秒杀指针!!!MySQL 日期时间加减mysql 查询条件之外的数据_mysql 查询符合条件的数据查linux的操作系统版本,如何查看Linux操作系统版本?将String类型转换成Map数据类型使用uuid做MySQL主键,被老板,爆怼一顿C语言中的字符串函数和字符函数linux服务器中毒排查--基础篇C# ASCII码字符转换