当前位置: 首页 > news >正文

排序

插入排序(最有价值)

类似于摸牌

InsertSort:O(N^2);最好:O(N)

最坏情况:逆序有序

最好情况:O(N)顺序有序

比冒泡排序实际应用更高效

以下是单趟排序,实现多趟需要再嵌套一个for循环,控制end的初值由0到n-1

void PrintArray(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}// 时间复杂度:O(N^2) 逆序
// 最好的情况:O(N)  顺序有序
void InsertSort(int* a, int n)
{// [0, end] end+1for (int i = 0; i < n - 1; ++i){int end = i;int tmp = a[end + 1];while (end >= 0){if (tmp > a[end]){a[end + 1] = a[end];--end;}else{break;}}a[end + 1] = tmp;}
}

冒泡排序:

BubbleSort:O(N^2);最好:O(N)

最好情况:O(N),包含标志位即可实现,表示第一次就没有发生交换,也就是说前一个总比后一个大,结束

先选出一个最大的,交换到最后一个位置。

第一个数进行n-1次交换,也就是小于n次交换,n-j(j=0)

第二个数进行n-2次交换,也就是小于n-1次交换,n-j(j=1)

第n个数进行n-n次交换,也就是小于n-(n-1)次交换,n-j(j=n-1)

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}void BubbleSort(int* a, int n)
{for (int j = 0; j < n; j++){bool exchange = false;for (int i = 1; i < n - j; i++){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = true;}}if (exchange == false)break;}//for (int i = 0; i < n-1; i++)//{//	if (a[i] > a[i+1])//	{//		Swap(&a[i], &a[i+1]);//	}//}
}

希尔排序

类似于插入排序,但是存在gap的间隔

ShellSort:平均O(N^1.3)

以上是分组排序,可以替换成多组并排

gap随着n进行变化

越到后面的每一次都可能比设想小,不能完全按逆序去算,因为前面已经排过了

最后一轮,gap=1,同时已经非常接近有序了。累计挪动大约n次

void ShellSort(int* a, int n)
{int gap = n;// gap > 1时是预排序,目的让他接近有序// gap == 1是直接插入排序,目的是让他有序while (gap > 1){//gap = gap / 2;gap = gap / 3 + 1;//+1可以保证最后一次一定是1for (int i = 0; i < n - gap; ++i){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}/*for (int j = 0; j < gap; ++j){for (int i = j; i < n-gap; i += gap){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}*/
}

选择排序

Selectsort:O(N^2);最好:O(N^2)

最小的和左边换,最大的和右边换

void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;while (begin < end){int mini = begin, maxi = begin;for (int i = begin + 1; i <= end; ++i){if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}//循环结束后mini是更新出来的最小的数值//max是最大的Swap(&a[begin], &a[mini]);//如果最大的值和最小的值是两个互换的位置,begin大和end小//min(end)和begin互换后,此时begin是最小的值,但是max存的是begin位置为最大值if (maxi == begin){//为了检测上一个交换的原位置是不是最大值//如果是最大值,则找最大值的新位置,也就是minimaxi = mini;}Swap(&a[end], &a[maxi]);++begin;--end;}
}

堆排序:

HeapSort:O(N*logN)

void AdjustDown(int* a, int size, int parent)
{int child = parent * 2 + 1;while (child < size){// 假设左孩子小,如果假设错了,更新一下if (child + 1 < size && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}// 升序
void HeapSort(int* a, int n)
{// O(N)// 建大堆for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, n, i);}// O(N*logN)int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}

快速排序:

有序情况下,快排很吃亏。因为快排的key选的是第一个数,在有序情况下,导致划分出的两个子序列长度极度不均衡,一个子序列可能只包含一个元素(即key本身),而另一个子序列包含了几乎所有剩余元素。以下有优化算法解决这个问题

越接近二分,快排越快

思想:

选一个关键字key,一般都是第一个数。

一个L,找比key大的,一个R,找比key小的。找到了就交换一下。相等的在哪都行,不用LR交换,否则死循环

然后将比key小的放左边,比key大的放右边

L和R相遇之后,和key交换,划分大小两边的分界线

注意:

为什么相遇位置比key小?因为右边先走

        相遇有两种情况:

        R遇见L。说明R没有找到比key小的,直到遇到L

        L遇见R。R先走,找到小的停下来了。同时L没有找到比key大的,都比key小,直到遇到R

如果L先走就保证不了,因为L找大,以找大为前提的话,相遇位置可能是比key大的

所以:左边做key,R先走。右边做key,L先走(三数选中就不会出现这种情况,不可能存在一边的是=数都比key大或者小)

while循环,在循环体内自增到不满足循环体的条件之后还会走完这个循环,就出现错误,所以要在循环体内部,也就是自增的这个循环加上控制条件

交换的时候不能和key交换,如果和key交换代表着数组和一个局部变量换位置了,并没有改变数组里的数字,所以要写成和a[keyi]交换

left不能从key+1开始,要从key开始比较,否则会出现以下情况:

这种写法坑很多的同时,在有序排列还会很不占优势:

QuickSort:O(N*logN)

void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;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]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);}
}

hoare版本单趟排序:O(N)

// hoare
int PartSort1(int* a, int begin, int end)
{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]);return left;
}

优化算法:

三数取中值法选key:

int GetMidi(int* a, int begin, int end)
{int midi = (begin + end) / 2;// begin end midi三个数选中位数,也就是不大不小的值if (a[begin] < a[midi]){if (a[midi] < a[end])return midi;else if (a[begin] > a[end])return begin;elsereturn end;}else{//a[begin] > a[midi]if(a[midi] > a[end]){return midi;}else if(a[begin] > a[end]){return begin;}else{return end;}}
}void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int midi = GetMidi(a, begin, end);//这里还是选择了最左边的值作为key,选哪都可以//然后再选出中间大小的值当做下面算法里的keySwap(&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]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}

与插入排序结合:

优化效果一般

当待排序区间长度小于等于 10 时,采用插入排序进行优化,此时快排就减少了很大一部分递归,保证了在数据很大的情况下,栈不会溢出

void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;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]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);}
}

挖坑法单趟排序:O(N)

方便写一点,不用管先走的问题

// 挖坑法
int PartSort2(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;
}

挖坑法和hoare版本的单趟排序结果可能不同

前后指针法:O(N)

1、cur遇到比key大的值,++cur

2、cur遇到比key小的值,++prev,交换prev和cur的值,++cur

3、cur出界后,交换prev和key的值

prev只有需要交换的时候才往前走,所以prev要么紧跟cur,要么和cur间隔比key大的值,等待下一次交换

int PartSort3(int* a, int begin, int end)
{int midi = GetMidi(a, begin, end);Swap(&a[midi], &a[begin]);int keyi = begin;int prev = begin;int cur = prev + 1;while (cur <= end){if (a[cur] < a[keyi] && ++prev != cur)Swap(&a[prev], &a[cur]);++cur;//本来是else内的,但是cur都需要++}Swap(&a[prev], &a[keyi]);keyi = prev;return keyi;
}

非递归排序:

递归排序:

递归排序是指在排序算法的设计中,通过函数自身调用自身来解决问题的排序方法。以快速排序为例,它的基本思想是选择一个基准元素,将数组分为两部分,使得左边部分的元素都小于等于基准元素,右边部分的元素都大于等于基准元素。然后对左右两部分分别递归地进行排序,直到子数组的长度为 1 或 0(即已经有序)

非递归排序:

非递归排序不依赖函数自身调用自身来实现排序,而是使用迭代的方式,通常借助数据结构如栈或队列来模拟递归的过程。以快速排序的非递归实现为例,可以使用一个栈来保存待排序的子数组的边界信息。开始时,将整个数组的边界信息(起始下标和结束下标)压入栈中,然后在循环中从栈中取出一个子数组的边界信息,进行划分操作,将划分后的左右子数组的边界信息再压入栈中,直到栈为空

QuickSortNonR:

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 = PartSort3(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);
}

归并排序:

后续递归

借助一个tmp数组,比较好大小之后再拷贝回去,再释放tmp数组

MergeSort:O(N*log(N))

一共log(N)层,一层N个


void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin >= end)return;int mid = (begin + end) / 2;// [begin, mid][mid+1, end]_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid + 1, end, tmp);// [begin, mid][mid+1, end]归并int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}//把tmp数组拷贝回去memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}//首先,递归的时候需要一个区间//其次,有malloc,要是递归自己,那每次还会生成一个空间//所以要借助一个子函数_MergeSort(a, 0, n - 1, tmp);free(tmp);
}

测试排序的性能对比


http://www.mrgr.cn/news/62831.html

相关文章:

  • 中小企业设备资源优化:Spring Boot系统实现
  • 【JavaEE】【多线程】进阶知识
  • 通过自定义指令实现图片懒加载
  • docker上传离线镜像包到Artifactory
  • gitblit 学习-hook功能
  • SpringMVC执行流程(视图阶段JSP、前后端分离阶段)、面试题
  • 第十五章数据管理成熟度评估
  • 新160个crackme - 088-[KFC]fish‘s CrackMe
  • Telegram bot教程:通过BotFather设置Telegram bot的命令菜单
  • Java Executor ScheduledThreadPoolExecutor 总结
  • DBeaver如何查看ER图
  • Python定义与调用函数
  • 【AI时代】普通程序员想投身AI大模型行业,该如何快速入局
  • DAY67WEB 攻防-Java 安全JNDIRMILDAP五大不安全组件RCE 执行不出网
  • 服务器宝塔安装哪吒监控
  • 数据结构(8.5_1)——归并排序
  • 通过QAxObject关闭已经打开的指定名称的Word文档
  • 【安装配置教程】一、windows安装并配置java8
  • RabbitMQ怎么保障消息的可靠性
  • aab上架谷歌市场流程(apk)
  • python爬取旅游攻略(1)
  • 强化学习数学基础学习(三)
  • 【随笔】为什么transformer的FFN先升维后降维FFN的作用
  • 搜维尔科技:Manus数据手套在水下捕捉精确的手指动作, 可以在有水的条件下使用
  • 全面解析云渲染:定义、优势、分类与发展历程
  • java-参数传递与接收