快速排序

基本思想:

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

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

相关文章

来自专栏张善友的专栏

弹出式模态窗体选择文本控件

2006年就要到来了,最近比较忙,很少更新blog,今天发一个模态窗体选择文本控件辞旧迎新.新年在发几个asp.net2.0 webPart控件同各位分享: ...

1907
来自专栏大内老A

开发自己的Data Access Application Block[下篇]

上接:[原创] 我的ORM: 开发自己的Data Access Application Block - Part I 4. Database 下面来介绍重中之重...

2236
来自专栏xingoo, 一个梦想做发明家的程序员

【插件开发】—— 6 SWT 复杂控件使用以及布局

前文回顾: 1 插件学习篇 2 简单的建立插件工程以及模型文件分析 3 利用扩展点,开发透视图 4 SWT编程须知 5 SWT简单控件的使用与布局搭...

2349
来自专栏技术之路

sqlserver 的事务和c#的事务

sql的事务 1 sql 2 create database model 3 go 4 use model 5 go 6 create table ...

1919
来自专栏跟着阿笨一起玩NET

treeview 绑定文件夹和文件

451
来自专栏Golang语言社区

GO语言 TCP传输实例

package main import ( "net" "fmt" ) var ( maxRead = 1100 msgStop = []byt...

3396
来自专栏跟着阿笨一起玩NET

从sql server 中读取二进制图片

391
来自专栏木宛城主

曾今的代码系列——自己的分页控件+存储过程实现分页

项目里面的测试代码,仅供参考 LoginByAjax <title>Ajax登陆</title> <script src="Scripts/c...

1855
来自专栏自由而无用的灵魂的碎碎念

小项目分享---混色器

编写代码的同志们一般懂美术的就少了,偶也是,什么色轮、三维加色等等。虽然看过一些书籍(如内田广由纪的《配色基础原理》),不过还是一知半解的。

963
来自专栏互联网开发者交流社区

STC-单片机控制系统

1113

扫码关注云+社区