快速排序算法

快速排序思想

看网上讲快速排序半天才搞懂，总结一下，快速排序核心思想是保证每个元素其所有左边元素比其小，所有右边元素比其大。这样理解最简单，具体是通过迭代来实现的。
闲来没事，用各种语言实现了一下，当作一个小练习，直接上代码：

OC实现

-(void)quickSortWithArray:(NSMutableArray *)array left:(NSInteger)left right:(NSInteger)right{
    if( left >= right )  return;
    
    NSInteger i = left;
    NSInteger j = right;
    NSUInteger pivot = [[array objectAtIndex:i] integerValue];
    while (i != j) {
        while (i < j && [[array objectAtIndex:j] integerValue] >= pivot) {
            j-- ;
        }
        while (i < j && [[array objectAtIndex:i] integerValue] <= pivot) {
            i++ ;
        }
        
        if (i < j) {
            [array exchangeObjectAtIndex:i withObjectAtIndex:j];
        }
    }
    
    [array exchangeObjectAtIndex:left withObjectAtIndex:i];
    
    [self quickSortWithArray:array left:left right:i-1];
    [self quickSortWithArray:array left:i+1  right:right];
    
}

Swift实现：

    func quickSort(array: inout [NSInteger] , left:NSInteger , right:NSInteger ) -> () {
        if left >= right {
            return;
        }
        var i = left;
        var j = right;
        let pivot = array[i];
        
        while i != j {
            
            while i<j && array[j] >= pivot {
                 j -= 1 ;
            }
            
            
            while i<j && array[i] <= pivot {
                i += 1 ;
            }
            
            if (i < j) {
            array.swapAt(i, j);
            }
        }
        array.swapAt(i, left)
        
        self.quickSort(array: &array, left: left, right: i-1 );
        self.quickSort(array: &array, left: i+1, right:right );
        
    }

JS实现：

            function quickSort(array, left, right){
                 if(left >= right){
                     return;
                 }
                 var i = left;
                 var j = right;
                 let pivot = array[i];
                 while(i != j){
                        while (i<j && array[j] >= pivot){
                            j --;
                        }

                        while (i<j && array[i] <= pivot){
                            i ++;
                        }
                        var p = array[i] ;
                        array[i] = array[j];
                        array[j] = p ;

                 }
                    var p = array[i] ;
                    array[i] = array[left];
                    array[left] = p ;
                
                this.quickSort(array, left, i-1);
                this.quickSort(array, i+1, right);

             }

python实现：

def QuickSort(list, left, right):

    if left >= right:
        return
    i = left;
    j = right;
    pivot = list[left]

    while i != j:
        while(i < j) and (list[j] >= pivot):
            j -= 1;
        while(i < j) and (list[i] <= pivot):
            i += 1;
        list[i],list[j] = list[j],list[i];

    list[left], list[i] = list[i], list[left];

    QuickSort(list, left, i-1);
    QuickSort(list, i+1, right);