澳门新萄京官方网站-www.8455.com-澳门新萄京赌场网址

澳门新萄京官方网站:中快速排序的学习,快速

2019-10-12 作者:www.8455.com   |   浏览(144)

最近看了一句话,说的是在现实生活中,会写字的人不见得会写出好文章,学习编程语言就像是学会了写字,学会了编程语言并不一定能写出好程序。

废话不多说,直接上图:

具体的8种排序算法的实现,请前往我的GitHub。点我过去

算法之旅 | 快速排序法

HTML5学堂-码匠:前几期“算法之旅”跟大家分享了冒泡排序法和选择排序法,它们都属于时间复杂度为O(n^2)的“慢”排序。今天跟大家分享多种排序算法里使用较广泛,速度快的排序算法 —— 快速排序法 [ 平均时间复杂度为O (n logn) ]。

澳门新萄京官方网站:中快速排序的学习,快速排序法。Tips 1:关于“算法”及“排序”的基础知识,在此前“选择排序法”中已详细讲解,可点击文后的相关文章链接查看,在此不再赘述。

Tips 2:如果无特殊说明,本文的快速排序是从小到大的排序。

我觉得就是很有道理,以前读书的时候,基本学完了C#中的语法知识,算是入了个门,但是一到写程序就毫无头绪,做出来的程序就像是小学生日记,仅仅只是用一些简单的api把功能拼凑起来,没有一点逻辑性,毫不美观优雅。

澳门新萄京官方网站 1

1、冒泡排序:

冒泡算法是一种基础的排序算法,这种算法会重复的比较数组中相邻的两个元素。如果一个元素比另一个元素大(小),那么就交换这两个元素的位置。重复这一比较直至最后一个元素。这一比较会重复n-1趟,每一趟比较n-j次,j是已经排序好的元素个数。每一趟比较都能找出未排序元素中最大或者最小的那个数字。这就如同水泡从水底逐个飘到水面一样。冒泡排序是一种时间复杂度较高,效率较低的排序方法。其空间复杂度是O(n)。
  1, 最差时间复杂度 O(n^2)
  2, 平均时间复杂度 O(n^2)

实现思路
  1,每一趟比较都比较数组中两个相邻元素的大小
  2,如果i元素小于i-1元素,就调换两个元素的位置
  3,重复n-1趟的比较

快速排序法的原理

快速排序是一种划分交换排序,它采用分治的策略,通常称其为分治法。

所以我决定慢慢的开始学习算法知识,虽然我数学很烂,逻辑能力差到极点,看这些算法的代码看的我是心态爆炸,真的头皮发麻,只有长期坚持学习,一点一点的慢慢进步了。

20160916153212716.png

冒泡排序代码实现

  (void) bubbleSort:(NSMutableArray *)array{
//遍历`数组的个数`次
/*
 i = 0 的时候,j的相邻两个位置都要比较排一下位置:  第1次i循环冒泡出arr_M中最小的
 j = 0 的时候:arr_M = 41235
 j = 1 的时候:arr_M = 42135
 j = 2 的时候:arr_M = 42315
 j = 3 的时候:arr_M = 42351
 i = 1;         第2次i循环冒泡出剩余最小的  以此类推
 ……  ……
 */
for (int i = 0; i < array.count;   i) {

    //遍历数组的每一个`索引`(不包括最后一个,因为比较的是j 1)
    for (int j = 0; j < array.count-1 - i;   j) {

        //根据索引的`相邻两位`进行`比较`
        if (array[j] < array[j 1]) {

            [array exchangeObjectAtIndex:j withObjectAtIndex:j 1];
        }

    }
} NSLog(@"冒泡排序:%@",array);}

分治法

基本思想:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解决这些子问题,然后将这些子问题的结果组合成原问题的结果。

 

图片名词解释:
n: 数据规模
k:“桶”的个数
In-place: 占用常数内存,不占用额外内存
Out-place: 占用额外内存
(本文代码戳这里)

2、选择排序:

    实现思路:
    1. 设数组内存放了n个待排数字,数组下标从1开始,到n结束。
  1. i=1
       3. 从数组的第i个元素开始到第n个元素,寻找最小的元素。(具体过程为:先设arr[i]为最小,逐一比较,若遇到比之小的则交换)
       4. 将上一步找到的最小元素和第i位元素交换。
       5. 如果i=n-1算法结束,否则回到第3步

复杂度:
  平均时间复杂度:O(n^2)
  平均空间复杂度:O(1)

基本原理

从序列中任选一个数作为“基准”;

所有小于“基准”的数,都挪到“基准”的左边;所有大于等于“基准”的数,都挪到“基准”的右边;

在这次移动结束之后,该“基准”就处于两个序列的中间位置,不再参与后续的排序;

针对“基准”左边和右边的两个子序列,不断重复上述步骤,直到所有子序列只剩下一个数为止。

快速排序是分治法中的一种常见排序算法,主要运用递归求解。

1.冒泡排序

大多数人接触的第一个算法估计就是冒泡排序了,不再赘述。
冒泡也有改进:
1.在某次遍历中如果没有数据交换则说明全部有序,后续的遍历就可以省去。
2.保存最后一次进行交换的位置,下一次比较到此处就停止。
3.鸡尾酒排序,从底到高然后从高到底。

选择排序代码实现

  (void)selectSort:(NSMutableArray *)array{
for (int i=0; i<array.count; i  ) {

    for (int j=i 1; j<array.count; j  ) {

        if (array[i]<array[j]) {

            [array exchangeObjectAtIndex:i withObjectAtIndex:j];

        }
    }
}
NSLog(@"选择排序:%@",array);}

原理图解

现有一个序列为 [8, 4, 7, 2, 0, 3, 1],如下演示快速排序法如何对其进行排序。

澳门新萄京官方网站 2

算法思想是将一个数组分为小于等于基准数的子数组和大于基准数的子数组,然后通过递归调用,不断对这两个子数组进行排序,直到数组元素只有0个或1个元素时,停止递归,再将各个排好序的子数组加起来,最终就得到了排好序的数组。

2.选择排序

选择排序就是每次选择数组中最大(小)的数放到数组最后(理解意思即可)。表现稳定(无论给定的数组是怎样的都是O(n2))

3、快速排序:

实现思路:
  1. 从数列中挑出一个元素,称为 "基准"(pivot),
  2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分割之后,该基准是它的最后位置。这个称为分割(partition)操作。
  3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
  快速排序是基于分治模式处理的,对一个典型子数组A[p...r]排序的分治过程为三个步骤:
    1.分解:
    A[p..r]被划分为俩个(可能空)的子数组A[p ..q-1]和A[q 1 ..r],使得
    A[p ..q-1] <= A[q] <= A[q 1 ..r]
    2.解决:通过递归调用快速排序,对子数组A[p ..q-1]和A[q 1 ..r]排序。
    3.合并。

递回的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递回下去,但是这个算法总会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

复杂度:
  平均时间复杂度:O(n^2)
  平均空间复杂度:O(nlogn) O(nlogn)~O(n^2)

实现快速排序的步骤分解

 

3.插入排序

每次都将一个待排序的数插入到前面已经排好序的子序列中的适当位置,知道全部插入完毕。
改进:待插入的元素之前的序列是已排好序的,结合二分查找进行。

快速排序代码实现:

>   (void)quickSort:(NSMutableArray *)array low:(int)low high:(int)high{
if(array == nil || array.count == 0 || low >= high){
    NSLog(@"注意快速排序条件");
    return;
}

//取中值
int middle = low   (high - low)/2;
NSNumber *prmt = array[middle];
int i = low;
int j = high;

//开始排序,使得left<prmt 同时right>prmt
while (i <= j) {
    //        while ([array[i] intValue] < [prmt intValue]) {
    //该行与下一行作用相同

    while ([array[i] compare:prmt] == NSOrderedAscending) {
        i  ;
    }
    //        while ([array[j] intValue] > [prmt intValue]) {
    //该行与下一行作用相同

    while ([array[j] compare:prmt] == NSOrderedDescending) {
        j--;
    }

    if(i <= j){
        [array exchangeObjectAtIndex:i withObjectAtIndex:j];
        i  ;
        j--;
    }
    NSLog(@"快速排序排序中:%@",array);
}
if (low < j) {
    [self quickSort:array low:low high:j];
}
if (high > i) {
    [self quickSort:array low:i high:high];
}}

选择“基准”,并将其从原始数组分离

先获取基准的索引值,再使用splice数组方法取出基准值。

澳门新萄京官方网站 3

Tips:该实例中, 基准的索引值 = parseInt(序列长度 / 2)

Tips:splice方法会改变原始数组。例如,arr = [1, 2, 3]; 基准索引值为1,基准值为2,原始数组变为arr = [1, 3];

步骤如下:

4.希尔排序

希尔排序是插入排序的改进,插入排序每次只能移动一步,而希尔排序每次可以向前移动一大步,之后再取小步数移动,到最后就成了插入排序,但此时序列几乎已经排好了,此时再进行插入排序会很快。

4、插入排序:

实现思路:
  1. 从第一个元素开始,认为该元素已经是排好序的。
  2. 取下一个元素,在已经排好序的元素序列中从后向前扫描。
  3. 如果已经排好序的序列中元素大于新元素,则将该元素往右移动一个位置。
  4. 重复步骤3,直到已排好序的元素小于或等于新元素。
  5. 在当前位置插入新元素。
  6. 重复步骤2。
  复杂度:
  平均时间复杂度:O(n^2)
  平均空间复杂度:O(1)

  (void)inserSort:(NSMutableArray *)array{
for (int i = 0; i < array.count; i  ) {
    NSNumber *temp = array[i];
    int j = i-1;
     while (j >= 0 && [array[j] compare:temp] == NSOrderedDescending) {
        [array replaceObjectAtIndex:j 1 withObject:array[j]];
        j--;
    }
    [array replaceObjectAtIndex:j 1 withObject:temp];
    NSLog(@"插入排序排序中:%@",array);
}}

遍历序列,拆分序列

与“基准”比较大小,并拆分为两个子序列

小于“基准”的数存储于leftArr数组当中,大于等于“基准”的数存储于rightArr数组当中

澳门新萄京官方网站 4

Tips:当然,也可以将 小于等于“基准”的数存于leftArr,大于“基准”的数存于rightArr

由于要遍历序列,将每一个数与“基准”进行大小比较,所以,需要借助for语句来实现

澳门新萄京官方网站 5

1. 选择一个基准值

5.归并排序

归并排序是创建在归并操作上的一种有效的排序算法,效率为O(nlogn),归并排序的实现分为递归实现与非递归(迭代)实现。递归实现的归并排序是算法设计中分治策略的典型应用,我们将一个大问题分割成小问题分别解决,然后用所有小问题的答案来解决整个大问题。归并排序算法主要依赖归并(Merge)操作。归并操作指的是将两个已经排序的序列合并成一个序列的操作。

5、归并排序:

归并排序是建立在归并操作上的一种有效的排序算法,算法主要采用分治法(Divide and Conquer)的一个非常典型的应用。归并排序的算法复杂度为O(N*logN),需要的额外的空间跟数组的长度N有关系,实现归并排序最简单的方法是将两个数组重新整合到第三个数组中。通常对于一个数组我们对前半部分进行排序,然后进行后半部分进行排序,实现原地归并操作,不过需要额外的空间存储数组。假设数据中有8个元素,先分为四组进行比较,之后分为两组进行比较,最后分为一组进行比较,这样就衍生出来两种方法,一种是自顶向下的归并排序,一种是自底向上的归并排序。

实现思路:
1.把序列分成元素尽可能相等的两半。
2.把两半元素分别进行排序。
3.把两个有序表合并成一个。

递归调用,遍历子序列并组合子序列的结果

定义一个函数,形参用于接收数组

  1. function quickSort(arr) { };

实现递归调用遍历子序列,用concat数组方法组合子序列的结果

澳门新萄京官方网站 6

2. 将数组分为两个子数组:小于基准值的元素和大于基准值的元素

6.快速排序

在平均状况下,排序n个元素要O(nlogn)次比较。在最坏状况下则需要O(n^2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他O(nlogn)算法更快,因为它的内部循环可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治策略(Divide and Conquer)来把一个序列分为两个子序列。步骤为:

  • 从序列中挑出一个元素,作为"基准"(pivot).
  • 把所有比基准值小的元素放在基准前面,所有比基准值大的元素放
    基准的后面(相同的数可以到任一边),这个称为分区(partition)操作。
  • 对每个分区递归地进行步骤1~3,递归的结束条件是序列的大小是0或1,这时整体已经被排好序了。
    快排优化
    对于分治算法,当每次划分时,算法若都能分成两个等长的子序列时,那么分治算法效率会达到最大。也就是说,基准的选择是很重要的。选择基准的方式决定了两个分割后两个子序列的长度,进而对整个算法的效率产生决定性影响。

6.希尔排序

希尔排序是以插入排序为基础的一种快速的排序算法。因为在大规模乱序数组中使用插入排序很慢,因为它只会交换相邻的两个元素,因此,如果越小的元素越是靠后,那么操作的复杂度将会大大提升,所以,人们把插入排序进行了改良,变成了希尔排序。
希尔排序的思想:希尔排序的思想是使数组中任意间隔为 h 的元素都是有序的。这样的数组为 h 有序数组。换句话说,一个 h 有序数组就是 h 个互相独 的有序数组编织在一起 成的一个数组。在进行排序时,如果 h 很大,我们就能将元素动到很远的地方,为实现更小的 h 有序创造方便。用这种方式,对于任意以 1 结尾的 h 序列,我们都能够将数组排序。这就是希尔排序。
如果您还想了解更多的希尔排序,可参看 点我链接

判断子序列的长度

递归调用的过程中,子序列的长度等于1时,则停止递归调用,返回当前数组。

澳门新萄京官方网站 7

3. 对这两个子数组进行排序

7.堆排序

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构(通常堆是通过一维数组来实现的),并同时满足堆的性质:即子结点的键值总是小于(或者大于)它的父节点。
我们可以很容易的定义堆排序的过程:

  • 创建一个堆
  • 把堆顶元素(最大值)和堆尾元素互换
  • 把堆的尺寸缩小1,并调用heapify(A, 0)从新的堆顶元素开始进行堆调整
  • 重复步骤2,直到堆的尺寸为1

7.基数排序

原理实现:
基数排序是另外一种比较有特色的排序方式,它是怎么排序的呢?我们可以按照下面的一组数字做出说明:12、 104、 13、 7、 9
(1)按个位数排序是12、13、104、7、9
(2)再根据十位排序104、7、9、12、13
(3)再根据百位排序7、9、12、13、104
这里注意,如果在某一位的数字相同,那么排序结果要根据上一轮的数组确定,举个例子来说:07和09在十分位都是0,但是上一轮排序的时候09是排在07后面的;同样举一个例子,12和13在十分位都是1,但是由于上一轮12是排在13前面,所以在十分位排序的时候,12也要排在13前面。
所以,一般来说,10基数排序的算法应该是这样的?
(1)判断数据在各位的大小,排列数据;
(2)根据1的结果,判断数据在十分位的大小,排列数据。如果数据在这个位置的余数相同,那么数据之间的顺序根据上一轮的排列顺序确定;
(3)依次类推,继续判断数据在百分位、千分位......上面的数据重新排序,直到所有的数据在某一分位上数据都为0。

复杂度分析.jpg

其中,d 为位数,r 为基数,n 为原数组个数。
在基数排序中,因为没有比较操作,所以在复杂上,最好的情况与最坏的情况在时间上是一致的,均为 O(d * (n r))。

快速排序法完整代码

澳门新萄京官方网站 8

 

8.计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。
作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。

8.堆排序

堆排序的空间复杂度为O(1),时间复杂度为O(nlogn)。
如果你想了解更多关于堆排序,可参考点击链接

快速排序法的效率

接着对子数组重复以上3步,直到子数组无法分解(子数组只有0个或1个元素时)

9.基数排序

基数排序也是非比较的排序算法,对每一位进行排序,从最低位开始排序,复杂度为O(kn),为数组长度,k为数组中的数的最大的位数;

  • 取得数组中的最大数,并取得位数;
  • arr为原始数组,从最低位开始取每个位组成radix数组;
  • 对radix进行计数排序(利用计数排序适用于小范围数的特点);

具体的8种排序算法的实现demo,请前往我的GitHub。点我前往

时间复杂度

最坏情况:每一次选取的“基准”都是序列中最小的数/最大的数,这种情况与冒泡排序法类似(每一次只能确定一个数[基准数]的顺序),时间复杂度为O(n^2)

最好情况:每一次选取的“基准”都是序列中最中间的一个数(是中位数,而不是位置上的中间),那么每次都把当前序列划分成了长度相等的两个子序列。这时候,第一次就有n/2、n/2两个子序列,第二次就有n/4、n/4、n/4、n/4四个子序列,依此类推,n个数一共需要logn次才能排序完成(2^x=n,x=logn),然后每次都是n的复杂度,时间复杂度为O(n logn)

 

澳门新萄京官方网站,10.桶排序

桶排序 (Bucket sort)的工作的原理:假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排)

  • 设置一个定量的数组当作空桶;
  • 遍历输入数据,并且把数据一个一个放到对应的桶里去;
  • 对每个不是空的桶进行排序;
  • 从不是空的桶里把排好序的数据拼接起来。

空间复杂度

最坏情况:需要进行n‐1 次递归调用,其空间复杂度为 O(n)

最好情况:需要logn次递归调用,其空间复杂度为O(logn)

可以使用函数递归重复上述过程,在递归函数中必须满足2个条件

算法的稳定性

快速排序是一种不稳定排序算法

例如:现有序列为[1, 0, 1, 3],“基准”数字选择为第二个1

在第一轮比较之后,变成了[0, 1, 1, 3],左序列为[0],右序列为[1, 3](右序列的1是此前的第一个1)

不难发现,原序列的两个1的先后顺序被破坏了,改变了先后顺序,自然就是“不稳定”的排序算法了

1.基线条件——指满足某个条件以后,函数不在调用自身进行递归

关于O

在此前的“冒泡排序法”一文当中,我们详细讲解过O是什么,在此就不多说了,直接上图吧

澳门新萄京官方网站 9

2.递归条件——满足递归条件就调用自身函数进行递归

相关文章链接

选择排序法

冒泡排序法

 

我看的书举例是使用Python代码实现的快速排序,代码如下:

 1 def quicksort(array):
 2     if len(array) < 2: #基线条件:为空或者只包含一个元素的数组是“有序”的
 3         return array 
 4     else:#递归条件
 5         pivot = array[0] 
 6         less = [i for i in array[1:] if i<= pivot]#由所有小于等于基准值的元素组成的数组
 7         greater = [i for i in array[1:] if i> pivot]#由所有大于基准值的元素组成的子数组
 8         return quicksort(less)   [pivot]   quicksort(greater)
 9 
10 
11 print(quicksort([10, 5, 2, 3]))

 

在这段代码里,首先满足递归条件时,取得一个基准数,基准数通常为数组的第一个元素,然后分成两个子数组,一个是小于等于基准数的子数组和大于基准数的子数组,不断进行递归调用对这两个子数组进行排序,最后得到排序好的数组。

书中讲解看完后,头脑里很快就有了思绪,但是当我想把上面的代码转换成C#时,就摸不着头脑,打脑壳的遭不住,因为在C#里并不能像上面一样简简单单的就实现,最主要的就是C#中数组不能通过直接相加来合并。

 

所以还是在网上看了不少C#快速排序的详解后写出了以下代码:

 1         /// <summary>
 2         /// 快速排序对数组进行升序排序
 3         /// </summary>
 4         /// <param name="array">要排序的数组</param>
 5         /// <param name="leftIndex">从左边遍历的第一个数的索引</param>
 6         /// <param name="rightIndex">从右边遍历的第一个数的索引</param>
 7         public static void QuickSort(int[] array, int leftIndex, int rightIndex)
 8         {
 9             if (leftIndex >= rightIndex)//基线条件
10                 return;
11             int n = leftIndex;
12             int m = rightIndex;
13             int pivot = array[leftIndex];
14             while (n != m)
15             {
16                 for (; n < m; m--)
17                 {
18                     if (array[m] < pivot)
19                     {
20                         array[n] = array[m];//交换位置
21                         break;
22                     }
23                 }
24                 for (; n < m; n  )
25                 {
26                     if (array[n] > pivot)
27                     {
28                         array[m] = array[n];
29                         break;
30                     }
31                 }
32             }
33             array[n] = pivot;//循环完成后已经按照小于基准数和大于基准数左右排好序,基准数放中间。
34             QuickSort(array, leftIndex, n - 1);//对着两个子数组进行递归
35             QuickSort(array, n   1, rightIndex);
36         }

 

网上快速排序的思路如上,甚至来说基线条件和我在书中看见的都已经完全不一样,并且和书中的逻辑也不太相同,只是依旧是分治法解决问题。

不仅是分出两个子数组,而是对当前的数组进行排序,排序过程也不好理解,从右至左循环,找出比基准数大的数,再从左至右循环,找出比基准数小的数,然后将两个数字调换位置,到最后只剩一个数的时候,就是基准数该在的位置,把基准数放到这个位置。

所以我足足想了2天,才能够独立写出上面的快速排序代码,不过我已经不知道我到底是真真切切理解了排序的思路,还是说因为看了太久,已经把排序的方式背在脑中了,真是悲哀,聪明的小伙伴一定一下就能学会,我却想了两天连自己也不清楚到底想明白没有了。

 

最后,我依旧有一个疑问,快速排序的时间复杂度是O(nlogn),那么上面的Python代码依旧是O(nlogn)吗?

新声明数组,然后将他们赋值,再合并,这样的操作会影响时间复杂度吗?

甚至我想用Linq语法

1             int[] less = (from i in array where i < pivot select i).ToArray();
2             int[] greater = (from i in array where i > pivot select i).ToArray();

返回的数组甚至还是排好序的,那我直接用将这两个数组和基准数加起来不是更简单吗?我已经完全懵逼了,不知道时间复杂度是如何计算的,学习的长路真是漫漫啊!

本文由澳门新萄京官方网站发布于www.8455.com,转载请注明出处:澳门新萄京官方网站:中快速排序的学习,快速

关键词: