快速排序

基本思想:

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

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 条评论
登录 后参与评论

相关文章

来自专栏ACM算法日常

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

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

1382
来自专栏窗户

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

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

663
来自专栏云时之间

NLP入门之形式语言与自动机学习(一)

任何一门科学都有其自身的理论基础,计算机科学也是这样.大家现在看看计算机的技术变化的很快,现在我们很流行的框架和工具很有可能几年内就会变成过时的东西.但是计算机...

4176
来自专栏云时之间

NLP入门之形式语言与自动机学习(一)

第一篇:集合与推理方法 1:我们为什么要学习形式语言与自动机 任何一门科学都有其自身的理论基础,计算机科学也是这样.大家现在看看计算机的技术变化的很快,现在我们...

1K13
来自专栏牛客网

深信服面试 C++/云计算面经

1955
来自专栏desperate633

LeetCode 121. Best Time to Buy and Sell Stock题目Solution

假设有一个数组,它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如,一次买卖股票),设计一个算法来找出最大利润。 样例 给出一...

693
来自专栏chenjx85的技术专栏

leetcode-202-Happy Number

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

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

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

3505
来自专栏落影的专栏

程序员进阶之算法练习(二十三)

前言 趁着8月还没结束,更新一篇算法练习。 正文 1. Alyona and mex 题目链接 题目大意: mex()定义:mex(arr)是 数组arr的...

4047
来自专栏数说工作室

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

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

2816

扫码关注云+社区