操纵排序结果,稳定排序365体育官网

0.基本概念

记录:待排序的项目

关键词:决定排序结果

稳定性:相同关键词的记录保持原来的相对次序

冒泡排序

冒泡排序算法的运营如下:

  1. 相比相邻的要素。假使第一个比第三个大,就交流他们八个。
  2. 对每一对周围元素作同样的做事,从开始率先对到最终的终极一对。那步做完后,最后的因素会是最大的数。
  3. 针对具有的要素重复以上的步骤,除了最后2个。
  4. 不止每一次对越来越少的要素重复上边的步子,直到未有其余一对数字需求相比。

日子复杂度O(n^二),空间复杂度O(壹),稳定排序:即一律的因素在排序后先后未有变动

代码完成:

static int[] bubbleSort(int[] arr) {
    for (int i=0; i<arr.length; i++) { //0~N-1 次循环
        //一轮比较后找到最大的元素,放到下标arr.length-1-i位置
        for (int j=0; j<arr.length-1-i; j++) {
            if (arr[j] > arr[j+1]) {
                swap(arr, j+1, j); //交互元素
            }
        }
    }
    return arr;
}

助记码
i∈[0,N-1)//循环N-1遍
    j∈[0,N-1-i)//每遍循环要处理的无序部分
    swap(j,j+1)  //两两排序(升序/降序)

1.一插入排序(Insertion Sort)

算法思想

一种简单直观的排序算法,工作原理是由此创设有序类别:对于未排序数据,在已排序体系中从后迈入扫描,找到相应岗位并插入。

 365体育官网 1

算法描述

具体算法描述如下:

  1. 从第三个要素起头,该因素得以认为曾经被排序
  2. 取出下一个成分,在早就排序的因素种类中从后迈入扫描
  3. 假若该因素(已排序)大于新因素,将该因素移到下一职位
  4. 再也步骤叁,直到找到已排序的因素小于只怕等于新因素的职位
  5. 将新成分插入到该任务后
  6. 再也步骤2~5

设若比较操作的代价比置换操作大的话,能够利用二分查找法来裁减相比较操作的数量。该算法能够认为是插入排序的几个变种,称为二分查找插入排序。

c++语言完结

void insertSort(MyArray &arr)
{
    for (int i = 1; i < arr.len();i++)
    {
        int current = i;
        while ((arr[current]>arr[current - 1]) && (current - 1) >= 0)
        {
            arr.swap(current, (current - 1));
            current--;
        }
    }
}

\注:为便宜描述排序算法,使用了自个儿自个儿做的数组类,代码请见最后。*

算法分析

1.稳定的

二.最棒状态:(n-一)

最棒状态正是,类别已经是升序排列了,在那种情景下,要求开始展览的可比操作需(n-一)次即可。

最坏情况:n(n-壹)/二

三.最坏情状便是,类别是降序排列,那么此时亟待展开的相比较共有n(n-1)/2回:第3个成分相比较3遍,第二个因素比较贰回…第n个因素相比较n-3回,求和为n(n-1)/2。

四.平均复杂度:O(n二)

平均来说插入排序算法复杂度为O(n二)。因此,插入排序不吻合对于数据量相比大的排序应用。不过,假使须要排序的数据量一点都不大,例如,量级小于千,那么插入排序依然几个不利的挑选。插入排序在工业级库中也富有广阔的使用,在STL的sort算法和stdlib的qsort算法中,都将插入排序作为快捷排序的增加补充,用于少量因素的排序(平时为7个或以下)。

选料排序

干活规律如下:首先在未排序种类中找到最小(大)成分,存放到排序种类的开局地方,然后,再从剩余未排序成分中继承查找最小(大)成分,然后嵌入已排序系列的最终。以此类推,直到全部因素均排序完结。

时光复杂度O(n^贰),空间复杂度O(1),不安定的排序

代码达成:

static int[] selectSort(int[] arr) {
    for (int i=0; i<arr.length; i++) {
        int min = i;
        //找到i下标起始的序列中的最小元素
        for (int j=i+1; j<arr.length; j++) {
            if (arr[min] > arr[j]) {
                min = j;
            }
        }
        swap(arr, i, min);
    }
    return arr;
}

1.贰希尔排序

算法思想

也称递减增量排序算法,是插入排序的一种更急速的更正版本。希尔排序是非稳定排序算法。

1.改正依照

  • 插入排序在对大致已经排好序的数码操作时,功能高,即能够达到线性排序的频率
  • 但插入排序壹般的话是没用的,因为插入排序每趟只可以将数据移动一个人

二.算法盘算

希尔排序通过将比较的全套成分分为多少个区域来进步插入排序的性质。那样可以让多少个因素得以一回性地朝最终地方前进一大步。然后算法再取更加小的幅度举行排序,算法的尾声一步正是平时的插入排序,然而到了那步,需排序的数目大致是已排好的了(此时插入排序较快)。

一个越来越好精晓的希尔排序完成

数组表,将数组列在多个表中并对列排序(用插入排序)。重复那进度,可是每一趟用更加长的列来开始展览。最终整个表就唯有1列了。将数组转换至表是为着越来越好地了解那算法,算法本身只是对原数组进行排序(通过扩大索引的宽度,例如是用i
+= step_size而不是i++)。

例如,若是有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10
],假若我们以小幅度为5伊始举行排序,大家能够由此将那列表放在有伍列的表中来越来越好地描述算法,这样他们就应有看起来是如此:

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

下一场咱们对每列举行排序:

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

将上述四行数字,依序接在一起时大家获取:[ 10 14 73 25 23 13 27 94 33 39
25 59 94 65 82 45 ].那时十曾经移至正确地方了,然后再以三为宽度举行排序:

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

排序之后成为:

10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

终极以一上升幅度实行排序(此时尽管简单的插入排序了)。

c++语言达成

*注:那里运用的增长幅度为每便除二(即为唐NaderShell最早建议的版本)

void shellSort(MyArray &arr)
{
    int gap = arr.len() / 2;
    while (gap >= 1)
    {
        //对每组插入排序;
        for (int k = 0; k < gap; k++)
        {
            for (int i = 1+k; i < arr.len(); i += gap)
            {
                int current = i;
                while ((arr[current] > arr[current - gap]) && (current - gap) >= 0)
                {
                    arr.swap(current, (current - gap));
                    current -= gap;
                }
            }
        }
        gap /= 2;//by Donald Shell
    }
}

算法分析

1.不稳定

贰.宽度与复杂度

上涨幅度的采取是希尔排序的根本片段。只要最后上涨幅度为一别样步长类别都能够干活。算法最先导以一定的升幅举办排序。然后会继续以自然幅度进行排序,最后算法以小幅为一拓展排序。当步长为一时,算法变为插入排序,那就确定保障了数码一定会被排序。

唐Nader Shell最初提议步长选取为

365体育官网 2

再者对步长取半直到步长达到一。即便这么取可以比

365体育官网 3

类的算法(插入排序)越来越好,但这么还是有缩减平均时间和最差时间的退路。恐怕希尔排序最珍视的地点在于当用较小幅排序后,从前用的较大幅面照旧是上行下效的。比如,若是2个数列以大幅5举行了排序然后再以步长叁进展排序,那么该数列不仅是以大幅三有序,而且是以急剧伍有序。借使不是这么,那么算法在迭代经过中会打乱在此之前的顺序,那就不会以如此短的时刻成功排序了。

365体育官网 4

已知的最佳步长体系是由Sedgewick建议的(一, 5, 1九, 四一,
10九,…),该种类的项来自

365体育官网 5

365体育官网 6

那多个算式。那项商讨也申明“相比在希尔排序中是最主要的操作,而不是换来。”用这么步长种类的希尔排序比插入排序要快,甚至在小数组中比迅速排序和堆排序还快,不过在涉及大气数目时希尔排序依旧比赶快排序慢。

另1个在大数组中表现不错的幅度种类是(斐波那契数列除去0和1将剩余的数以黄金分区比的两倍的幂进行演算获得的数列):(一,
九, 3肆, 1八2, 836, 402伍, 一九〇五一, 9035八, 4284八1, 203403伍, 9651787, 45806244,
21737807陆, 拾31612713,…)

插入排序

办事规律是由此创设有序系列,对于未排序数据,在已排序系列中从后迈入扫描,找到呼应地方并插入。

诚如的话,插入排序都施用in-place在数组上贯彻。具体算法描述如下:

  1. 从第二个成分开端,该因素得以认为曾经被排序
  2. 取出下贰个成分,在已经排序的因素体系中从后迈入扫描
  3. 借使该因素(已排序)大于新因素,将该因素移到下一个人置
  4. 再一次步骤3,直到找到已排序的成分小于恐怕等于新因素的地方
  5. 将新成分插入到该任务后
  6. 再一次步骤2~5

光阴复杂度O(n^二),空间复杂度O(1),稳定的排序

落到实处代码:

static int[] insert(int[] arr) {
    for (int i=1; i<arr.length; i++) {
        int temp = arr[i], j=0;//保存当前待排序元素
        for (j=i-1; j>=0 && arr[j] > temp; j--) {//从后往前遍历
            arr[j+1] = arr[j];//对数值大的,元素后移
        }
        arr[j+1] = temp;//将待排序元素插入到正确位置
    }
    return arr;
}

贰.壹冒泡排序(Bubble Sort)

算法思想

穿梭调换反序对:

是1种简易的排序算法。它再次地拜会过要排序的数列,3遍相比较几个成分,若是她们的次第错误就把他们调换过来。走访数列的做事是重新鸿基土地资产拓展直到未有再需求调换,相当于说该数列已经排序完毕。这一个算法的名字由来是因为越小的要素会经过调换稳步“浮”到数列的上方。

365体育官网 7

算法实现

  1. 正如相邻的成分。倘诺第3个比第3个大,就沟通他们七个。
  2. 对每1对周围成分作同样的干活,从上马率先对到终极的最后一对。那步做完后,最后的因素会是最大的数。
  3. 本着富有的成分重复以上的步调,除了最后四个。
  4. 绵绵每趟对更少的要素重复上面的步子,直到没有别的①对数字要求比较。

c++语言达成

void bubbleSort(MyArray &arr)
{
    for (int i = 0; i < arr.len(); i++)
    {
        for (int j = arr.len()-1; j >= i+1; j--)
        {
            if (arr[j] > arr[j - 1])
                arr.swap(j, j - 1);
        }
    }
}

算法分析

1.稳定

2.复杂度

冒泡排序对

365体育官网 8

个品种供给O(

365体育官网 9

)的比较次数,且可以原地排序。固然那些算法是最简易询问和落到实处的排序算法之1,但它对于个别要素之外的数列排序是很未有作用的。

冒泡排序是与插入排序拥有卓殊的运行时刻,不过二种算法在急需的置换次数却不小地分化。在最棒的境况,冒泡排序需求

365体育官网 10

次沟通,而插入排序只要最多

365体育官网 11

换成。冒泡排序的贯彻(类似上面)平时会对曾经排序好的数列迟钝地运作(

365体育官网 12

),而插入排序在这么些例子只须要

365体育官网 13

个运算。因而不少现代的算法教科书防止使用冒泡排序,而用插入排序替换之。冒泡排序假诺能在里边循环第2回运维时,使用二个旗标来表示有无要求调换的恐怕,也可以把最棒的复杂度下落到

365体育官网 14

。在那些状态,已经排序好的数列就无沟通的急需。若在历次走访数列时,把走访顺序反过来,也能够稍微地改良功效。有时候称为苦味酒排序,因为算法会从数列的壹端到另一端之间穿梭往返。

三个对冒泡有趣的改革地精排序请移步作者的下一篇文章
http://www.cnblogs.com/yatesxu/p/5402127.html

 

希尔排序

希尔排序是插入排序的晋级版,希尔排序是基于插入排序的以下两点性质而提议立异措施的:
一.插入排序在对差不离已经排好序的数码操作时,功效高,即能够高达到规定的分数线性排序的频率
2.但插入排序壹般的话是不行的,因为插入排序每趟只可以将数据运动一人
希尔排序通过将相比的整套要素分为多少个区域来进步插入排序的属性。那样能够让两个因素得以叁回性地朝最后地方前进一大步。然后算法再取更小的宽窄实行排序,算法的末段一步就是普通的插入排序,可是到了那步,需排序的数码差不多是已排好的了(此时插入排序较快)。
比方有1个相当小的数额在三个已按升序排好序的数组的背后。如若用复杂度为O(n2)的排序(冒泡排序或插入排序),可能会进行n次的比较和交换才能将该数额移至正确地方。而希尔排序会用较大的上涨幅度移动多少,所以小数码只需举行个别相比和沟通即可到正确地方。
即希尔排序通过调动插入步长来兑现更迅捷高效的数码调整。

宽度的接纳是希尔排序的关键片段。只要最终上涨幅度为1别样步长类别都能够干活。DonaldShell最初建议步长采纳为
n/二并且对步长取半直到步长达到壹。已知的最棒步长种类是由Sedgewick建议的(1,
5, 1玖, 四一,
十玖,…),那项研究也标志“比较在希尔排序中是最主要的操作,而不是换到。”用这么步长种类的希尔排序比插入排序要快,甚至在小数组中比火速排序和堆排序还快,可是在涉及大气数量时希尔排序还是比神速排序慢。

时刻复杂度O(nlog^二n),括号内是n乘以logn的平方,空间复杂度O(壹),不安宁的排序

代码完结:

static int[] shellInsert(int[] arr) {
    int foot = arr.length / 2;//步长初始化
    while (foot >= 1) {
        for (int i=1; i<arr.length; i++) {
            int temp = arr[i], j=0;
            for (j=i-foot; j>=0 && arr[j] > temp; j=j-foot) {
                arr[j+foot] = arr[j];
            }
            arr[j+foot] = temp;
        }
        foot /= 2;//调整步长
    }

    return arr;
}

二.二高速排序 Quick Sort

算法思想

频频交换反序对:使用分治法(Divide and
conquer)策略来把多个队列(list)分为四个子体系(sub-lists)。

算法完结

  1. 从数列中挑出叁个成分,称为”基准”(pivot),
  2. 再也排序数列,全部因素比基准值小的摆放在基准前边,全数因素比基准值大的摆在基准的末端(相同的数能够到任1边)。在这一个分区停止以往,该标准就处于数列的中游地方。那么些号称分区(partition)操作。
  3. 递归地(recursive)把小于基准值成分的子数列和当先基准值成分的子数列排序。

递归的最尾巴部分意况,是数列的尺寸是零或1,约等于永远都曾经被排序好了。纵然平昔递归下去,不过那个算法总会结束,因为在历次的迭代(iteration)中,它至少会把叁个因素摆到它聊到底的地点去。

算法分析

1.不稳定

2.复杂度

在平均情形下,排序n个项目要Ο(n
log
n)次相比较。在最坏现象下则必要Ο(n贰)次相比较,但那种现象并不常见。事实上,火速排序平时显明比其他Ο(n
log n)算法更加快,因为它的里边循环(inner
loop)能够在大部的架构上很有成效地被完毕出来。

三个实例

365体育官网 15

c++语言达成

void quickSortProcess(MyArray &arr, int m, int n)
{
    if (m < n)
    {
        int i = m;
        int j = n;
        while (i <= j)
        {
            while ((arr[m] >= arr[i]) && (i <=n))
                i++;
            while ((arr[m] < arr[j]) && (j >=m + 1))
                j--;
            if (i < j)
                arr.swap(i, j);
        }
        arr.swap(m, j);
        quickSortProcess(arr, m, j - 1);
        quickSortProcess(arr, j + 1, n);
    }
}
void quickSort(MyArray &arr)
{
    quickSortProcess(arr, 0, arr.len() - 1);
}

 

快快排序

高效排序使用分治法(Divide and
conquer)策略来把二个行列(list)分为三个子连串(sub-lists)。
步骤为:

  1. 从数列中挑出三个要素,称为”基准”(pivot),
  2. 再度排序数列,全数比基准值小的成分摆放在基准前边,全体比基准值大的因素摆在基准前面(相同的数能够到任1边)。在那么些分区甘休现在,该条件就高居数列的高级中学级地点。这些名称为分区(partition)操作。
  3. 递归地(recursively)对小于基准值成分的子数列和超乎基准值成分的子数列排序。

递归到最底部时,数列的轻重是零或一,也正是现已排序好了。这么些算法一定会截至,因为在历次的迭代(iteration)中,它起码会把一个成分摆到它最后的岗位去。

时间复杂度O(nlogn),,空间复杂度O(logn),不稳定的排序

原地(in-place)分区的版本代码:
原地分区算法,它分区了标记为”左侧(left)”和”右侧(right)”的队列部分,借由活动小于等于a[pivotIndex]的有所因素到子系列的启幕,留下全部大于的因素接在他们后边。在这几个进程它也为规范成分找寻最终摆放的职分,相当于它回传的值。

static int partition(int[] arr, int left, int right) {
    int pivot = left-1;//初始基准下标设定
    //默认基准值为arr[right]
    //这里可以先随机选择一个基准值,然后将其和arr[right]交换即可

    for ( ;left <= right; left++) {
        //注意等号比较重要,如果不加等号,则需要在for循环结束后swap(arr, ++pivot, right);即将基准值放到正确的位置。
        if (arr[left] <= arr[right]) {
            swap(arr, ++pivot, left);//将小于等于基准值的元素移动到序列开头
        }
    }
    return pivot;//返回调整后的基准值下标
}

迅猛排序算法:

static void quick(int[] arr, int left, int right) {
    if (left >= right) return;//边界检查
    int pivot = partition(arr, left, right);
    quick(arr, left, pivot-1);
    quick(arr, pivot+1, right);
}

3.一精选排序(Selection sort)

算法思想

是一种简易直观的排序算法。它的做事原理如下。首先在未排序体系中找到最小(大)成分,存放到排序类别的开端位置,然后,再从剩余未排序成分中继续搜寻最小(大)元素,然后嵌入已排序类别的末段。以此类推,直到全体因素均排序完结。

选取排序的基本点优点与数据移动有关。假如某些成分位梁晓艳确的尾声地点上,则它不会被移动。选取排序每一回交换1对成分,它们当中至少有二个将被移到其最终地点上,由此对n个成分的表展开排序总共实行至多n-一回调换。在具备的完全依靠调换去运动成分的排序方法中,选取排序属于万分好的壹种。

365体育官网 16

c++语言实现

void selectSort(MyArray &arr)
{
    for (int i = 0; i < arr.len(); i++)
    {
        int maxLoc = i;
        for (int j = i; j < arr.len(); j++)
        {
            maxLoc = (arr[j] > arr[maxLoc]) ? j: maxLoc;
        }
        arr.swap(i, maxLoc);
    }
}

算法分析

1.不稳定

2.复杂度

择排序的调换操作介于

365体育官网 17

365体育官网 18

次以内。采纳排序的比较操作为

365体育官网 19

次以内。选拔排序的赋值操作介于

365体育官网 20

次之间。

相比次数

365体育官网 21

,相比较次数与重点字的开端状态无关,总的比较次数

365体育官网 22

。交流次数

365体育官网 23

,最棒状态是,已经稳步,沟通0次;最坏处境是,逆序,调换

365体育官网 24

次。沟通次数比冒泡排序较少,由于沟通所需CPU时间比相比较所需的CPU时间多,

365体育官网 25

值较小时,选用排序比冒泡排序快。

原地操作大约是挑选排序的唯1亮点,当方度(space
complexity)须要较高时,能够记挂选取排序;实际适用的场子尤其稀有。

归并排序

该算法是采用分治法(Divide and
Conquer)的3个可怜出众的运用,且各层分治递归能够而且展开。
归并操作(merge),也叫联合算法,指的是将五个已经排序的行列合并成四个队列的操作。归并排序算法重视归并操作。

时间复杂度O(nlogn),,空间复杂度O(n),稳定的排序

迭代法

  1. 报名空间,使其尺寸为三个曾经排序类别之和,该空间用来存放合并后的行列
  2. 设定多少个指针,最初地方分别为三个曾经排序类别的苗头地点
  3. 相比四个指针所指向的要素,接纳绝对小的成分放入到统一空间,并活动指针到下一个人置
  4. 再次步骤3直到某一指南针到达种类尾
  5. 将另1连串剩下的享有因素直接复制到合并系列尾

归并操作代码:

static void mergeProcess(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right-left+1];//合并空间
    int l = left;//左边序列起始下标
    int r = mid+1;//右边序列起始下标
    int id = 0;//合并空间起始下标

    while (l <= mid && r <= right) {//合并
        if (arr[l] < arr[r]) {//先放入小的
            temp[id++] = arr[l++];
        } else {
            temp[id++] = arr[r++];
        }
    }

    //合并剩余的序列
    while (l <= mid) temp[id++] = arr[l++];
    while (r <= right) temp[id++] = arr[r++];

    //将排好的序列复制到原序列
    for (int i=0; i<id; i++) {
        arr[left+i] = temp[i];
    }
}

递归归并排序:
事实上就是将类别先分割成二个个小的行列,然后再对小种类实行统1,同时在集合的历程中展开排序。

static void merge(int[] arr, int left, int right) {
    if (left >= right) return;
    int mid = (left+right) / 2;//找到分割点下标
    merge(arr, left, mid);//分割左
    merge(arr, mid+1, right);//分割右
    mergeProcess(arr, left, mid, right);//合并
}

非递归法 : 边界条件倒霉控制,易出错。
规律如下(假诺连串共有n个元素):

  1. 将体系每相邻七个数字实行统1操作,形成
    floor(n/二)个系列,排序后种种类别包罗四个因素
  2. 将上述体系再一次相会,形成floor(n/四)个连串,各类类别包罗七个因素
  3. 重新步骤2,直到全部因素排序完成

static void merge2(int[] arr) {
    int step = 1;//序列合并的子序列起始长度为1

    while (step <= arr.length) {
        int i=0;
        //将2个step长的序列合并为一个序列,长度加倍
        for ( ; i+2*step-1<arr.length; i += 2*step) {
            mergeP(arr, i, i+step-1, i+2*step-1);//合并2个子序列
        }

        //对长度不足2*step的序列尾进行合并,且最后一次整个序列的合并也由此完成
        if (i+step-1 < arr.length) {
            mergeP(arr, i, i+ step-1, arr.length-1);
        }
        step *= 2;
    }
}

//写法二
static void merge2(int[] arr) {
    int before = 1;//合并前序列长
    int after = 0;//合并后序列长度

    while (before <= arr.length) {
        after = before * 2;//将2个序列合并为一个序列,长度加倍
        int i=0;
        for ( ; i+after-1<arr.length; i += after) {
            mergeProcess(arr, i, i+before-1, i+after-1);//合并2个子序列
        }

        //对长度不足after的序列尾进行合并,且最后一次整个序列的合并也由此完成
        if (i+before-1 < arr.length) {
            mergeProcess(arr, i, i+ before-1, arr.length-1);
        }
        before = after;
    }
}

堆排序(Heapsort)

详细的堆排序内容,请移步http://www.cnblogs.com/yatesxu/p/5404929.html

算法思想

是指使用堆那种数据结构所布置的一种排序算法。堆积是1个类似完全二叉树的构造,并同时满足堆积的性质:即子结点的键值或索引总是小于(大概超越)它的父节点

真相上是四个淘汰赛

算法达成

1.堆节点的拜会

日常堆是通过1维数组来完成的。在数组开始地点为0的状态中:

  • 父节点i的左子节点在地点(二*i+1);
  • 父节点i的右子节点在职责(2*i+2);
  • 子节点i的父节点在地点floor((i-一)/二);

贰.堆的操作

在堆的数据结构中,堆中的最大值总是位于根节点。堆中定义以下两种操作:

  • 最大堆调整(马克斯_Heapify):将堆的前面子节点作调整,使得子节点永远小于父节点
  • 创造最大堆(Build_Max_Heap):将堆全部数据再一次排序
  • 堆排序(HeapSort):移除位在首先个数据的根节点,并做最大堆调整的递归运算

算法分析

1.不稳定

2.复杂度

堆排序的平分时间复杂度为

365体育官网 26

,空间复杂度为

365体育官网 27

堆排序实例

365体育官网 28

堆排序

动用堆那种数据结构所布署的一种排序算法。堆是三个看似完全二叉树的布局,并同时知足堆的属性:即子结点的键值或索引总是小于(大概抢先)它的父节点。
熟视无睹堆是经过壹维数组来促成的。在数组开端地点为0的图景中:
父节点i的左子节点在岗位(二i+1);
父节点i的右子节点在位置(2
i+2);
子节点i的父节点在职责floor((i-一)/2);

在堆的数据结构中,堆中的最大值总是位于根节点(在先行队列中运用堆的话堆中的最小值位于根节点)。
堆中定义以下两种操作:
最大堆调整(马克斯_Heapify):将堆的后面子节点作调整,使得子节点永远小于父节点
创办最大堆(Build_Max_Heap):将堆全部数据再度排序
堆排序(HeapSort):移除位在率先个数据的根节点,并做最大堆调整的递归运算

堆排序的长河:

  1. 将数组调整为最大堆
  2. 将最大堆的根节点,即当前堆的最大值和数组未排序部分的末尾三个值替换
  3. 再也调整最大堆,最大堆的数CEO度是冬日数组的尺寸
  4. 重复2,3步骤

//最大堆调整,id是待调整的元素下标,len是待调整的数组长度
//一般调整时认为待调整节点以后的元素是符合最大堆的分布规律的    
static void heapAdjust(int[] arr, int id, int len) {
    while (id*2 + 1 < len) {
        int child = id*2 + 1;//左孩子
        if (child+1 < len && arr[child+1] > arr[child]) {
            child++;//右孩子大于左孩子情况
        }

        if (arr[child] > arr[id]) {//右孩子大于父节点
            swap(arr, id, child);//替换
            id = child;//在新的节点上开启下一轮比较
        } else {
            break;
        }
    }
}

static int[] heapSort(int[] arr) {
    int n = arr.length;
    for (int i= n/2; i>=0; i--) {//生成最大堆
        heapAdjust(arr, i, n);
    }

    for (int i=n-1; i>0; i--) {//每次调整最大堆的数组长度
        swap(arr, i, 0);//当前堆的最大值和数组未排序部分的最后一个值替换
        heapAdjust(arr, 0, i);//调整最大堆
    }
    return arr;
}

归并排序 (Merge sort)

算法思想

归并操作(merge),也叫联合算法,指的是将多个已经排序的体系合并成贰个行列的操作。归并排序算法依赖归并操作。

算法达成

1.迭代法

  1. 申请空间,使其尺寸为四个已经排序种类之和,该空间用来存放在合并后的连串
  2. 设定多少个指针,最初地方分别为三个曾经排序类别的序曲地点
  3. 比较八个指针所指向的要素,采纳相对小的要素放入到联合空间,并活动指针到下壹岗位
  4. 再也步骤三直到某一指针到达类别尾
  5. 将另一系列剩下的享有因素直接复制到合并连串尾

2.递归法

原理如下(要是类别共有n个成分):

  1. 将系列每相邻多个数字举办合并操作,形成

365体育官网 29

个体系,排序后各种系列包蕴四个要素

  1. 将上述系列再度见面,形成

365体育官网 30

个连串,各种类别包罗八个要素

  1. 再一次步骤贰,直到全数因素排序完结

算法分析

1.稳定

2.复杂度

比较操作的次数介于

365体育官网 31

365体育官网 32

。 赋值操作的次数是

365体育官网 33

。归并算法的半空中复杂度为:Θ(n)

MyArray类

#include <iostream>
using namespace std;

class MyArray
{
    friend istream &operator>>(istream &is, MyArray &arr);
    friend  ostream &operator<<(ostream &os, const MyArray &arr);    
public:
    MyArray(int len = 32) :length(len)
    {
        ptrArr = new int[length];
        for (int i = 0; i < length; i++)
            ptrArr[i] = 0;
    };
    int len() const{ return length; }
    int& get(int i) const{ return ptrArr[i]; }
    void set(int loc, int num){ ptrArr[loc] = num; }
    void swap(int loc1, int loc2){ int tmp = ptrArr[loc1]; ptrArr[loc1] = ptrArr[loc2]; ptrArr[loc2] = tmp;}
    int& operator[](int i)const{ return get(i); }
private:
    int *ptrArr;
    int length;
};
#include"MyArray.h"
istream& operator>>(istream &is, MyArray &arr)
{
    for (int i = 0; i < arr.length; i++)
        is >> arr.ptrArr[i];
    return is;
}
ostream &operator<<(ostream &os, const MyArray &arr)
{
    for (int i = 0; i < arr.length; i++)
        cout << arr.ptrArr[i] << " ";
    return os;
}

相关文章