常用的排序算法（更新ing）
2020-04-17 本文已影响0人
MQ_Twist
没有撤退可言~
前言
就个人而言，可能和我所做的项目有关，排序算法在开发中用到的还没有在面试中用到的多，之前也手撕一些有关排序算法的，用进废退，好久不用都快忘完了，今天没事就简单的记录一下。
- 冒泡排序
冒泡排序是一种稳定排序算法。
时间复杂度:最好情况(初始情况就是正序)下是o(n),平均情况是o(n²) 。
/**
* 【冒泡排序】：相邻元素两两比较，比较完一趟，最值出现在末尾
* 第1趟：依次比较相邻的两个数，不断交换（小数放前，大数放后）逐个推进，最值最后出现在第n个元素位置
* 第2趟：依次比较相邻的两个数，不断交换（小数放前，大数放后）逐个推进，最值最后出现在第n-1个元素位置
* …… ……
* 第n-1趟：依次比较相邻的两个数，不断交换（小数放前，大数放后）逐个推进，最值最后出现在第2个元素位置
*/
void bublleSort(int *arr, int length) {
for(int i = 0; i < length - 1; i++) { //趟数
for(int j = 0; j < length - i - 1; j++) { //比较次数
if(arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
- 选择排序
选择排序是不稳定的排序方法。
时间复杂度：最好和平均情况下都是O(n²）。
/**
* 【选择排序】：最值出现在起始端
*
* 第1趟：在n个数中找到最小(大)数与第一个数交换位置
* 第2趟：在剩下n-1个数中找到最小(大)数与第二个数交换位置
* 重复这样的操作...依次与第三个、第四个...数交换位置
* 第n-1趟，最终可实现数据的升序（降序）排列。
*
*/
void selectSort(int *arr, int length) {
for (int i = 0; i < length - 1; i++) { //趟数
for (int j = i + 1; j < length; j++) { //比较次数
if (arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
- 直接插入排序
直接插入排序是稳定的排序算法。
时间复杂度：最好情况(初始情况就是正序)下是o(n),平均情况是o(n²)。
/**
* 插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有
* 序数据，算法适用于少量数据的排序，
* 插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当
* 位置上，直到全部插入完为止
*/
void insertSort2(int num[],int count)
{
int i,j;
for (i = 1; i < count; i++) {
if (num[i] < num[i - 1]) {
int temp = num[i];
for (j = i; j > 0; j--) {
if (num[j - 1] > temp) num[j] = num[j - 1];
else break;
num[j] = temp;
}
}
}
- 二分插入排序
二分插入排序是稳定的排序算法。
时间复杂度：最好情况(刚好插入位置为二分位置)下是O(log₂n),平均情况和最坏情况是o(n²)。
/**
* 算法的基本过程
*
*（1）计算 0 ~ i-1 的中间点，用 i 索引处的元素与中间值进行比较，如果 i 索引处的元素大，说明要插入的这个元素应该在中间值和刚加入i索引之间，反之，就是在刚开始的位置 到中间值的位置，这样很简单的完成了折半；
*（2）在相应的半个范围里面找插入的位置时，不断的用（1）步骤缩小范围，不停的折半，范围依次缩小为 1/2 1/4 1/8 .......快速的确定出第 i 个元素要插在什么地方；
*（3）确定位置之后，将整个序列后移，并将元素插入到相应位置。
*
*/
void insertSortBinary(int num[],int count)
{
int i,j;
for (i = 1; i < count; i++) {
if (num[i] < num[i - 1]) {
int temp = num[i];
int left = 0,right = i - 1;
while (left <= right) {
int mid = (left + right)/2;
if (num[mid] < temp) left = mid + 1;
else right = mid - 1;
}
//只是比较次数变少了，交换次数还是一样的
for (j = i; j > left; j--) {
num[j] = num[j - 1];
}
num[left] = temp;
}
}
}
- 希尔(插入)排序
希尔排序是非稳定排序算法。
时间复杂度：O(n^（1.3—2）)。
/**
* 算法的基本过程
*
* 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
* 随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，排序完成
*/
void shellSort(int num[],int count)
{
int shellNum = 2;
int gap = round(count/shellNum);
while (gap > 0) {
for (int i = gap; i < count; i++) {
int temp = num[i];
int j = i;
while (j >= gap && num[j - gap] > temp) {
num[j] = num[j - gap];
j = j - gap;
}
num[j] = temp;
}
gap = round(gap/shellNum);
}
}
- 快速排序
快速排序是非稳定的排序算法。
时间复杂度：最差为O(n^2)，平均为O(nlogn)，最好为O(nlogn)。
/**
* 算法的基本过程
*
* 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，
* 然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
*/
void quickSort(int num[],int count,int left,int right)
{
if (left >= right){
return ;
}
int key = num[left];
int lp = left; //左指针
int rp = right; //右指针
while (lp < rp) {
if (num[rp] < key) {
int temp = num[rp];
for (int i = rp - 1; i >= lp; i--) {
num[i + 1] = num[i];
}
num[lp] = temp;
lp ++;
rp ++;
}
rp --;
}
quickSort(num,count,left,lp - 1);
quickSort(num,count,rp + 1,right);
}
- 堆排序
堆排序是一个非稳定的排序算法。
时间复杂度：O(nlogn)。
/**
* 算法的基本过程
*
* 在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种操作：
* 1> 最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点。
* 2> 创建最大堆（Build Max Heap）：将堆中的所有数据重新排序。
* 3> 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算。
*/
void quickSort(int num[],int count,int left,int right)
{
if (left >= right){
return ;
}
int key = num[left];
int lp = left; //左指针
int rp = right; //右指针
while (lp < rp) {
if (num[rp] < key) {
int temp = num[rp];
for (int i = rp - 1; i >= lp; i--) {
num[i + 1] = num[i];
}
num[lp] = temp;
lp ++;
rp ++;
}
rp --;
}
quickSort(num,count,left,lp - 1);
quickSort(num,count,rp + 1,right);
}
后记
持续更新中。。。
