• 总所周知 快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用。
• 基本原理是
  数组a = [1,3,5,7,6,4,2]
  1 选定一个 基准 a[0]
  2 把比 a[0]小的放左边，比a[0]大的放右边. 中断递归如果少于两个数字 则不执行。
  3 然后再分别对两边 执行 1，2，3操作。
• 对快速排序 的 想法
  1 在待排序元素 大部分是有序的情况下， 速度 非常很快。
  2 在最差的情况下，速度就很慢了。 相当于冒泡了
  3 所以 快排的 优化， 定基准 非常重要，例如待排序是有序的，基准定在中间，xiao'lv
  4 时间复杂度为nlogn，不稳定排序

• Swift 极简版本
  import UIKit
  extension Array {
  var decompose : (head: Element, tail: [Element])? {
  return (count > 0) ? (self[0], Array(self[1..<count])) : nil
  }
  }

        func qsortDemo(input: [Int]) -> [Int] {
            if let (pivot, rest) = input.decompose {
                let lesser = rest.filter { $0 < pivot }//这里是小于于pivot基数的分成一个数组
                let greater = rest.filter { $0 >= pivot }//这里是大于等于pivot基数的分成一个数组
                return qsortDemo(lesser) + [pivot] + qsortDemo(greater)//递归 拼接数组
            } else {
                return []
            }
        }
  
        var a:[Int] = [1,2,4,6,2,4,3,7,8]
        qsortDemo(a)
  

///次方法来自http://blog.csdn.net/cg1991130/article/details/48274919

• swift 版本
  import UIKit

                    func quickSort(inout a:[Int],l:Int,r:Int){
                        
                        if l < r {
                            var i = l, j = r ,x = a[i]
                            while i < j && a[j] >= x{
                                j -= 1
                            }
                            if i < j {
                                a[i] = a[j]
                                i += 1
                            }
                            while i < j && a[i] < x {
                                i += 1
                            }
                            if i < j {
                                a[j] = a[i]
                                j -= 1
                            }
                           
                            a[i] = x
                            
                            quickSort(&a, l: l, r: i-1)
                            quickSort(&a, l: i+1, r: r)
                        }
                        
                        
                    }

                    var b = [8,7,6,5,4,3,2,1]

                     quickSort(&b, l: 0, r: 7)
                        
                        print(b)

• c版本

include <stdio.h>

            ///三个参数 a要排序的 数组， l扫左边的  r扫右边
            void quickSort(int a[],int l, int r){
                /// 左边要小于 右边才有意义
                if (l < r){
                    //保存 一下  ，基准定为X
                    int i = l, j = r, x = a[i];
                    
                    ///左边小于右边才开始循环，排序里面
                    while (i < j) {
                     
                        ///从 右边开始向左查找，小于 基准X的值。
                        while (i < j && a[j] >= x)
                            j--;
                        if (i < j)
                            a[i++] = a[j];///调换 他们的值
                        
                        ///该从左边开始向右查找 比基准x大与等于值
                        while (i < j && a[i] < x)
                            i++;
                        if (i < j)
                            a[j--] = a[i];
                    
                    }
                    ///然后把 x的值 赋值回去
                    a[i] = x;
                    
                    ///递归 左边
                    quickSort(a, l, i-1);
                    ///右边
                    quickSort(a, i+1, r);
                    
                }

            }


            int main() {
                
                int a[8] = {8,7,6,5,4,3,2,1};
                
                quickSort(a, 0, 7);
                
                for (int i = 0; i < 8; i++) {
                    printf("%d",a[i]);
                }
                printf("\n");
                return 0;
            }

• 看我那么可爱n(≧▽≦)n

• 关注我的微薄 (梁同桌)：http://weibo.com/tongrenyinsheng
• 个人博客： http://www.liangtongzhuo.com
• ios 个人写的app （同人音声）ASMR音乐