快速排序

基本思想:

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

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

相关文章

来自专栏用户2442861的专栏

腾讯2014校园招聘软件开发类笔试试题

http://blog.csdn.net/zs634134578/article/details/20938113

882
来自专栏李家的小酒馆

二叉树的层次遍历

二叉树的层次遍历 基本思想 借助队列来实现 首先初始化队列.然后将根结点压入队列 然后出队,输出出队元素的值, 如果存在左孩子.则左孩子入队 如果存在右孩子,则...

1980
来自专栏有趣的Python

算法与数据结构(五)二叉搜索树

二叉搜索树 (Binary Search Tree) 核心是解决问题。高效解决问题。 查找问题 Searching Problem: 查找问题是计算机中非常重...

2726
来自专栏猿人谷

总结---2

1.各种排序算法的时间复杂度和空间复杂度分析 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法, 冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。...

1628
来自专栏编程理解

数据结构(五):哈夫曼树(Huffman Tree)

哈夫曼树(或者赫夫曼树、霍夫曼树),指的是一种满二叉树,该类型二叉树具有一项特性,即树的带权路径长最小,所以也称之为最优二叉树。

862
来自专栏编程理解

数据结构(二):二叉搜索树(Binary Search Tree)

二分法的查找过程是,在一个有序的序列中,每次都会选择有效范围中间位置的元素作判断,即每次判断后,都可以排除近一半的元素,直到查找到目标元素或返回不存在,所以

821
来自专栏Vamei实验室

纸上谈兵: 左倾堆 (leftist heap)

我们之前讲解了堆(heap)的概念。堆是一个优先队列。每次从堆中取出的元素都是堆中优先级最高的元素。 在之前的文章中,我们基于完全二叉树(complete bi...

2879
来自专栏Linyb极客之路

2016 腾讯软件开发面试题(部分)

2016 腾讯软件开发面试题(不定项选择题【1-12】) 1、已知一棵二叉树,如果先序遍历的节点顺序是: ADCEFGHB ,中序遍历是: CDFEGHAB ,...

3608
来自专栏深度学习计算机视觉

java自定义构造二叉树及其遍历

首先:二叉树的建立 首先,我们采用广义表建立二叉树(关于广义表的概念,请查看百科的介绍:http://baike.baidu.com/view/203611.h...

2886
来自专栏静默虚空的博客

排序六 堆排序

堆的概念 在介绍堆排序之前,首先需要说明一下,堆是个什么玩意儿。 堆是一棵顺序存储的完全二叉树。 其中每个结点的关键字都不大于其孩子结点的关键字,这样的堆称为小...

17110

扫码关注云+社区