展开

关键词

C++ 经典排序算法

1.1.概述 冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。 它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。 走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。 这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端,故名。 1.2.算法原理: 冒泡排序算法的运作如下:(从后往前) 1.比较相邻的元素。如果第一个比第二个大,就交换他们两个。 2.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。 早了解和熟悉了排序过程后,我们发现,直接插入排序是一种稳定的原地排序算法。 所以在记录数较小、待排序序列基本有序情况下直接插入排序优于折半插入排序。此外,折半插入排序是不稳定的原地排序,实现起来也较复杂。 看了这么多比较经典的排序算法,有没有觉得算法真的是一个神奇的“道具”。

38120

排序算法笔记(C++版)

注: ①第一个算法给出了完整的测试程序,其余的为避免重复及节省空间,只显示排序算法部分代码 ②运行结果的程序耗时每次运行略有不同,仅供大致对比参考 1.冒泡排序 时间复杂度:O(n)[最好],O(n^2 [平均],O(n^2^)[最差]空间复杂度:O(1)代码: #include<iostream> #include<windows.h>//计时用 using namespace std; //冒泡排序算法 ; QueryPerformanceFrequency(&nFreq); QueryPerformanceCounter(&t1); //排序算法 int count (代码略) //排序算法 //int count = 0; for (int i = n - 1; i > 0; i--) { int max = i; //算法计时(代码略) //排序算法 int i, j; for (i = 1; i < n; i++) { int tmp = data[i];//待插入的值

17130
  • 广告
    关闭

    开发者专享福利,1988元优惠券限量发放

    带你体验博客、网盘相册搭建部署、视频渲染、模型训练及语音、文字识别等热门场景。云服务器低至65元/年,GPU15元起

  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    C++实现堆排序算法

    1.实现堆排序算法C++实现一个堆排序。 /*大根堆排序算法的基本操作: ① 初始化操作:将R[1..n]构造为初始堆; ② 每一趟排序的基本操作:将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换,然后将新的无序区调整为堆(亦称重建堆) 注意: ①只需做n - 1趟排序,选出较大的n - 1个关键字即可以使得文件递增有序。 ②用小根堆排序与利用大根堆类似,只不过其排序结果是递减有序的。 堆排序和直接选择排序相反:在任何时刻,堆排序中无序区总是在有序区之前, 且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。 StartIndex = MaxChildrenIndex; } else { //比较左右孩子均大则堆未破坏,不再需要调整 break; } } } //堆排序

    8930

    10种C++排序算法

    排序数组(10种排序) 下面博文,为早期学习写的,很不简洁,请参考上面题目的版本。 1.插入排序 /* * 1.插入排序 * 每次在末尾插入一个数字,依次向前比较,类似与抓扑克牌(插入排序,每次左边的子序列都是有序的) */ void insertsort(size_t dsize +n-1=n(n-1)/2 */ 2.冒泡排序 /* *2.冒泡排序,数从前向后冒泡比较,冒泡过程中,数列无序状态 */ void bsort(size_t dsize, int *arr) { /* *3.选择排序,每次找出数值最小的下标,交换未排序区域第一个与最小的(与冒泡的区别,只交换一次) */ void selecsort(size_t dsize, int *arr) { if /* 1. 6.快速排序 2.

    12710

    C++实现各种排序算法

    插入排序:直接插入排序、折半插入排序、希尔排序 交换排序:冒泡排序、快速排序 选择排序:简单选择排序、堆排序 #include<bits/stdc++.h> using namespace std; //直接插入排序 void st_insert_sort(vector<int>& nums) { int n = nums.size(); for(int i = 1; i < n; i+ nums[j + 1] = cur : nums[0] = cur; } } //二分插入排序 void bs_insert_sort(vector<int>& nums) { int n - 1; j >= high + 1; j--) { nums[j + 1] = nums[j]; } nums[high + 1] = cur; } } //希尔排序 <int>& nums, int step) { int n = nums.size(); for(int i = step; i < n; i++) { //从每组的第二个记录开始进行插入排序

    6720

    C++ STL之排序算法

    排序算法和查找算法差不多,也涉及到迭代器区间问题,关于该问题的注意事项就不在啰嗦了 一、全部排序sort、stable_sort sort是一种不稳定排序,使用时需要包含头文件algorithm 默认可以传两个参数或三个参数 第一个参数是要排序的区间首地址,第二个参数是区间尾地址的下一地址。如果只传入这两个地址的话,就按照升序对指定地址区间排序。 13 cout<<a[i]<<endl; 14 } 15 //降序 16 sort(a,a+9,greater<int>()); 17 cout<<"降序排序结果 二、部分排序partial_sort、partial_sort_copy 1 #include<iostream> 2 #include<algorithm> 3 using namespace ,放在_First到_Mid位置,剩下的在_Mid到_Last的元素不排序,pred是排序方式 15 partial_sort(num,num+3,num+10); 16 for(int

    40550

    C++经典算法题-排序法 - 改良的选择排序

    36.排序法 - 改良的选择排序 说明 选择排序法的概念简单,每次从未排序部份选一最小值,插入已排序部份的后端,其时间主要花费于在整个未排序部份寻找最小值,如果能让搜寻最小值的方式加 快,选择排序法的速率也就可以加快 ,Heap排序法让搜寻的路径由树根至最后一个树叶,而不是整个未排序部份,因而称之为改良的选择排序法。 建立好堆积树之后,树根一定是所有元素的最小值,您的目的就是: 将最小值取出 然后调整树为堆积树 不断重复以上的步骤,就可以达到排序的效果,最小值的取出方式是将树根与最后一个树叶节点交换,然后切下树叶节点 如此重覆步骤之后,由于使用一维阵列来储存堆积树,每一次将树叶与树根交换的动作就是将最小值放至后端的阵列,所以最后阵列就是变为已排序的状态。 其实堆积在调整的过程中,就是一个选择的行为,每次将最小值选至树根,而选择的路径并不是所有的元素,而是由树根至树叶的路径,因而可以加快选择的过程, 所以Heap排序法才会被称之为改良的选择排序法。

    18510

    C++经典算法题-排序法 - 改良的气泡排序

    ,它使用了旗标与右端左移两个方法来改进排序的效能,而Shaker排序法使用到后面这个观念进一步改良气泡排序法。 解法 在上面的气泡排序法中,交换的动作并不会一直进行至阵列的最后一个,而是会进行至MAX-i- 1,所以排序的过程中,阵列右方排序好的元素会一直增加,使得左边排序的次数逐渐减少,如我们的例子所示: 排序前 ,Shaker排序使用了这个概念,如果让左边的元素也具有这样的性质,让左右两边的元素都能先排序完成,如此未排序的元素会集中在中间,由于左右两边同时排序,中间未排序的部份将会很快的减少。 方法就在于气泡排序的双向进行,先让气泡排序由左向右进行,再来让气泡排序由右往左进行, 如此完成一次排序的动作,而您必须使用left与right两个旗标来记录左右两端已排序的元素位置。 一个排序的例子如下所示: 排序前:45 19 77 81 13 28 18 19 77 11 往右排序:19 45 77 13 28 18 19 77 11 [81] 向左排序:[11] 19 45 77

    45500

    C++经典算法题-合并排序

    40.Algorithm Gossip: 合并排序法 说明 之前所介绍的排序法都是在同一个阵列中的排序,考虑今日有两笔或两笔以上的资料,它可能是不同阵列中的资料,或是不同档案中的资料,如何为它们进行排序 解法 可以使用合并排序法,合并排序法基本是将两笔已排序的资料合并并进行排序,如果所读入的资料尚未排序,可以先利用其它的排序方式来处理这两笔资料,然后再将排序好的这两笔资料合并。 排序的精神是尽量利用资料已排序的部份,来加快排序的效率,小笔资料的 排序较为快速,如果小笔资料排序完成之后,再合并处理时,因为两笔资料都有排序了,所有在合并排序时会比单纯读入所有的资料再一次排序来的有效率 那么可不可以直接使用合并排序法本身来处理整个排序的动作?而不动用到其它的排序方式? 不过基本上分割又会花去额外的时间,不如使用其它较好的排序法来排序小笔资料,再使用合并排序来的有效率。 下面这个程式范例,我们使用快速排序法来处理小笔资料排序,然后再使用合并排序法处理合并的动作。

    21300

    C++经典算法题-快速排序法(三)

    39.Algorithm Gossip: 快速排序法(三) 说明 之前说过轴的选择是快速排序法的效率关键之一,在这边的快速排序法的轴选择方式更加快了 快速排序法的效率,它是来自演算法名书 Introduction 解法 先说明这个快速排序法的概念,它以最右边的值s作比较的标准,将整个数列分为三个部份, 一个是小于s的部份,一个是大于s的部份,一个是未处理的部份,如下所示 : ? 在排序的过程中,i 与 j 都会不断的往右进行比较与交换,最后数列会变为以下的状态: ? 然后将s的值置于中间,接下来就以相同的步骤会左右两边的数列进行排序的动作,如下所示: ? int main(void) { int number[MAX] = {0}; int i, num; srand(time(NULL)); printf("排序前 = rand() % 100; printf("%d ", number[i]); } quicksort(number, 0, MAX-1); printf("\n排序

    26310

    快速排序算法C++)介绍和简易实现

    快速排序算法,即一种递归地讲数组按一定大小标准分成两组,小的一组在前,大的一组排在后的算法。 有关快速排序算法的文章和图解,网络上已经很多了,但阅读理解起来可能稍有困难,接下来我们将看到更容易理解的快速排序算法。 (抽象的)数组只有基准一个元素(如下图第二排的“2”),排序完成。 快速排序算法示例 快速排序的复杂度 快排过程中需要移动元素的位置,很大程度上决定了时间复杂度。 《算法导论》第7章:快速排序 2.快速排序的时间复杂度nlogn是如何推导的??

    2.3K30

    C++经典算法题-快速排序法(二)

    38.Algorithm Gossip: 快速排序法(二) 说明 在快速排序法(一)中,每次将最左边的元素设为轴,而之前曾经说过,快速排序法的 加速在于轴的选择,在这个例子中,只将轴设定为中间的元素, 依这个元素作基准进行比较, 这可以增加快速排序法的效率。 41 24 36 11 19 64* 21* 69 45 76 [41 24 36 11 19 21] [64 69 45 76] 完成以上之后,再初别对左边括号与右边括号的部份进行递回,如此就可以完成排序的目的 int, int); int main(void) { int number[MAX] = {0}; int i, num; srand(time(NULL)); printf("排序前 = rand() % 100; printf("%d ", number[i]); } quicksort(number, 0, MAX-1); printf("\n排序

    16710

    C++经典算法题-选择、插入、气泡排序

    33.Algorithm Gossip: 选择、插入、气泡排序 说明 选择排序(Selection sort)、插入排序(Insertion sort)与气泡排序(Bubble sort)这三个排序方式是初学排序所必须知道的三个基本排序方式 解法 选择排序 将要排序的对象分作两部份,一个是已排序的,一个是未排序的,从后端未排序部份选择一个最小值,并放入前端已排序部份的最后一个,例如: 排序前:70 80 31 37 10 1 48 60 33 基本的气泡排序法可以利用旗标的方式稍微减少一些比较的时间,当寻访完阵列后都没有发生任何的交换动作,表示排序已经完成,而无需再进行之后的回圈比较与交换动作,例如: 排序前:95 27 90 49 80 58 在上面的例子当中,还加入了一个观念,就是当进行至i与i+1时没有交换的动作,表示接下来的 i+2至n已经排序完毕,这也增进了气泡排序的效率。 ("(1)选择排序\n(2)插入排序\n(3)气泡排序\n:"); scanf("%d", &i); switch(i) { case 1:

    31310

    C++经典算法题-基数排序

    41.Algorithm Gossip: 基数排序法 说明 在之前所介绍过的排序方法,都是属于「比较性」的排序法,也就是每次排序时 ,都是比较整个键值的大小以进行排序。 这边所要介绍的「基数排序法」(radix sort)则是属于「分配式排序」(distribution sort), 基数排序法又称「桶子法」(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯 ,将要排序的元素分配至某些「桶」中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog®m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的比较性排序法 解法 基数排序的方式可以采用LSD(Least sgnificant digital)或MSD(Most sgnificant digital), LSD的排序方式由键值的最右边开始,而MSD则相反, 接下来将这些桶子中的数值重新串接起来,成为以下的数列: 14, 22, 28, 39, 43, 55, 65, 73, 81, 93 这时候整个数列已经排序完毕;如果排序的对象有三位数以上,则持续进行以上的动作直至最高位数为止

    37310

    C++经典算法题-快速排序法(一)

    37.Algorithm Gossip: 快速排序法(一) 说明 快速排序法(quick sort)是目前所公认最快的排序方法之一(视解题的对象而定),虽然快速排序法在最差状况下可以达O(n2),但是在多数的情况下 ,快速排序法的效率表现是相当不错的。 快速排序法的基本精神是在数列中找出适当的轴心,然后将数列一分为二,分别对左边与右边数列进行排序,而影响快速排序法效率的正是轴心的选择。 这边所介绍的第一个快速排序法版本,是在多数的教科书上所提及的版本,因为它最容易理解, 也最符合轴心分割与左右进行排序的概念,适合对初学者进行讲解。 j 从数列左右方往左方找,直到找到小于 s 的数如果 i >= j,则离开回圈 如果 i < j,则交换索引i与j两处的值将左侧的轴与 j 进行交换 对轴左边进行递回对轴右边进行递回 透过以下演算法

    29310

    算法-排序算法-选择排序

    /** * 排序算法-选择排序 * 选择排序(Selection Sort)算法也是比较简单的排序算法,其思路比较直观。选择排序算法在每一步中选取最小值来重新排列,从而达到排序的目的。 * 选择排序算法通过选择和交换来实现排序,其排序流程如下: * (1)首先从原始数组中选择最小的1个数据,将其和位于第1个位置的数据交换。 至此,便完成了对原始数组的从小到大的排序。 * * 选择排序算法在对n个数据进行排序时,无论原数据有无顺序,都需要进行n-1步的中间排序。 * 这种排序方法思路很简单直观,但是缺点是执行的步骤稍长,效率不高。 size; i++) { ints[i] = (int)(Math.random() * 100 ); } System.out.println("排序前的数组

    25930

    C++经典算法题-Shell 排序法 - 改良的插入排序

    34.Algorithm Gossip: Shell 排序法 - 改良的插入排序 说明 插入排序法由未排序的后半部前端取出一个值,插入已排序前半部的适当位置,概念简单但速度不快。 排序要加快的基本原则之一,是让后一次的排序进行时,尽量利用前一次排序后的结果,以加快排序的速度,Shell排序法即是基于此一概念来改良插入排序法。 Shell首先将间隔设定为n/2,然后跳跃进行插入排序,再来将间隔n/4,跳跃进行排序动作,再来间隔设定为n/8、n/16,直到间隔为1之后的最 后一次排序终止,由于上一次的排序动作都会将固定间隔内的元素排序好 再来间隔设定为2 / 2 = 1,此时就是单纯的插入排序了,由于大部份的元素都已大致排序过了, 所以最后一次的插入排序几乎没作什么排序动作了: ? 后来还有人证明有其它的间隔选定法可以将Shell排序法的速度再加快;另外Shell排序法的概念也可以用来改良气泡排序法。

    23200

    算法-排序算法-冒泡排序

    /** * 排序算法-冒泡排序 * 冒泡排序(Bubble Sort)算法是所有排序算法中最简单、最基本的一种。 * 冒泡排序算法的思路就是交换排序,通过相邻数据的交换来达到排序的目的。 * 冒泡排序的思路: * (1)对数组中的各数据,依次比较相邻的两个元素的大小。 * (2)如果前面的数据大于后面的数据,就交换这两个数据。经过第一轮的多次比较排序后,便可将最小的数据排好。 * 冒泡排序算法在对n个数据进行排序时,无论原数据有无顺序,都需要进行(i = n-1)次的外层循环。 * 每次内部的排序随着步骤的递增,需要排序的数据逐步减少,所以需要 (n - i)次的内层循环,注意:i从1开始 */ import java.util.*; public class BubbleSort :" + Arrays.toString(ints)); } System.out.println("最终排序后的数组:" + Arrays.toString(ints)

    19920

    算法-排序算法-希尔排序

    /** * 排序算法-希尔排序 * 冒泡排序算法、选择排序算法和插入排序算法,虽然思路比较直观,但是排序的效率比较低。 * 对于大量的数据需要排序时,往往需要寻求其他更为高效的排序算法。 Shell排序算法便是其中一种 * Shell排序算法严格来说基于插入排序的思想,其又称为希尔排序或者缩小增量排序,思路如下: * (1)将有n个元素的数组分成n/2个数字序列,第1个数据和第n/2 * (3)然后,再变为n/4个序列,再次排序。 * (4)不断重复上述过程,随着序列减少最后变为一个,也就完成了整个排序。 size; i++) { ints[i] = (int)(Math.random() * 100 ); } System.out.println("排序前的数组 :" + Arrays.toString(ints)); } System.out.println("排序后的数组:" + Arrays.toString(ints))

    14920

    算法-排序算法-快速排序

    /** * 排序算法-快速排序 * 快速排序(Quick Sort)算法和冒泡排序算法类似,都是基于交换排序思想的。快速排序算法对冒泡排序算法进行了改进,从而具有更高的执行效率。 * 快速排序算法通过多次比较和交换来实现排序,过程如下: * (1)首先设定一个分界值,通过该分界值将数组分成左右两部分。 * (3)然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样将左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。 当左、右两部分各数据排序完成后,整个数组的排序也就完成了。 :" + Arrays.toString(ints)); quickSortFun(ints, 0, size - 1); System.out.println("排序后的数组

    15610

    扫码关注腾讯云开发者

    领取腾讯云代金券