快速排序

基本思想:

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

image

实现方案

首先任意选择数组一个数据作为关键数据,然后将所有比他小的数据都放在他的前面,所有比他大的数据放到他后面面,这个过程称为一次快速排序,接下去就是类似的递归操作,排序完成一轮后key左右两边的值继续相同排序

OC:

 NSMutableArray *arr = [[NSMutableArray alloc] initWithObjects:@(6), @(1),@(2),@(5),@(9),@(4),@(3),@(7),nil];
 [self quickSortArray:arr withLeftIndex:0 andRightIndex:arr.count - 1];

- (void)quickSortArray:(NSMutableArray *)arr withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex {
    
    if (leftIndex >= rightIndex) {
        return;
    }
    NSInteger i = leftIndex;
    NSInteger j = rightIndex;
    NSInteger key = [arr[i] integerValue];
    while (i < j) {
        while (i < j && [arr[j] integerValue] >= key) {// 从右边开始查找比基准数小的值
            j--;
        }
        // 谷歌币基准数小,则将查找到的小值调换到i的位置
        arr[i] = arr[j];
        
        while (i < j && [arr[i] integerValue] < key) {// 从左边开始查找比基准数大的值
            i++;
        }
        arr[j] = arr[i];
    }
    
    arr[i] = @(key);//将基准数放到正确位置
    // 第一次查找结束后进行左右两边查找,依次类推递归操作
    [self quickSortArray:arr withLeftIndex:leftIndex andRightIndex:i - 1];
    [self quickSortArray:arr withLeftIndex:i + 1 andRightIndex:rightIndex];
    NSLog(@"%@", arr);
}

Python: 别喷,根据oc改写的,哈哈哈哈

 arr = [7,5,8,4,3,6,9,2,1]
 print(arr)
 quick_sort(arr,0,len(arr)-1)
 print(arr)

def quick_sort(array,low,high):
    if low >= high:
        return
    i = low
    j = high
    key = arr[i]
    while i < j:

        while i < j and arr[j] >= key :
            j = j - 1

        arr[i] = arr[j]

        while i < j and arr[i] <= key :
            i = i + 1
        arr[j] = arr[i]
    arr[i] = key
    #以上结束一轮

    quick_sort(arr,low,i - 1)
    quick_sort(arr, i + 1, high)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏绿巨人专栏

函数式编程 : 一个程序猿进化的故事

3649
来自专栏ACM算法日常

水果Fruit(母函数) - HDU 2152

转眼到了收获的季节,由于有TT的专业指导,Lele获得了大丰收。特别是水果,Lele一共种了N种水果,有苹果,梨子,香蕉,西瓜……不但味道好吃,样子更是好看。 ...

1462
来自专栏ACM算法日常

LIS的简单应用:UVA-437

上一次紫芝详细地介绍了动态规划中的经典问题LIS,今天我们抽出一个类似思想的简单题目进行实践练习。

1053
来自专栏F_Alex

数据结构与算法(一)-初识

前言:一个程序员前期可能需要各种业务和编程的能力,但是后期如果想要提高就需要有一个扎实的基础,厚积薄发,所以最近抽空学了下数据结构与算法,颇有感触,学习过程虽然...

1172
来自专栏chenjx85的技术专栏

leetcode-202-Happy Number

3247
来自专栏窗户

scheme实现最基本的自然数下的运算

  教一个基本没编过什么程序的朋友scheme,为什么教scheme呢?因为他想学,因为一直听我鼓吹,而他觉得他自己多少有C语言一点基础,而又因为我觉得函数式才...

803
来自专栏小白的技术客栈

Python之面向对象程序设计-基础知识

面向对象是一种编程范式。范式是指一组方法论。编程范式是一组如何组织代码的方法论。编程范式指的是软件工程中的一种方法学。 主流的编程范式: OOP - 面向对象编...

3605
来自专栏ACM算法日常

神、上帝以及老天爷(递推) - HDU 248

HDU 2006'10 ACM contest的颁奖晚会隆重开始了!为了活跃气氛,组织者举行了一个别开生面、奖品丰厚的抽奖活动,这个活动的具体要求是这样的: ...

1712
来自专栏chenjx85的技术专栏

leetcode-53-Maximum Subarray(动态规划详解)

2164
来自专栏数说工作室

循环、分支...都可以在Python中用函数实现! | 函数式编程,打开另一个世界的大门

编程界有一位传奇人物——王垠,介绍一下他的退学经历,对,你没听错,退!学!经!历!: 2006年,从清华大学计算机系退学,在水木社区BLOG上发表了《清华梦的...

2956

扫码关注云+社区

领取腾讯云代金券