//
//  main.m
//  快速排序_练习
//
//  Created by AnchoriteFiliGod on 15/7/7.
//  Copyright (c) 2015年 赵宏亚. All rights reserved.
//

#import <Foundation/Foundation.h>

#pragma mark 快速排序_在main函数外边，直接创建函数方法
void sort(int a[],int left,int right)
{
    if (left >= right) { //如果左边的索引大于右边的索引代表已经整理完成一个组了，直接返回。
        return;
    }
    
    int i = left;
    int j = right;
    int key = a[left];
    
    while (i < j) { //控制在当组内寻找一遍
        while (i < j && key <= a[j]) {
            // 而寻找约束条件是
            // 1.找到一个小于或者大于key的数(大于或者小于取决于你想升序还是降序)
            // 2.如果没有符合条件1的，并且i与j的大小没有反转
            j --; // 向前寻找
        }
        
        /**
         找到一个这样的数后就把它赋给前面的被拿走的i的值(如果是第一次循环且key是a[left]，那么就是
         给key)
         */
        a[i] = a[j];
        
        while (i < j && key >= a[i]) {
            /**
             这是i在当前组内向前寻找，同上不过注意与key的大小关系停止循环和上面相反，
             因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反
             */
            i ++;
        }
        a[j] = a[i];
    }
    
    a[i] = key; // 当在本组内找完一遍以后就把中间数key回归
    sort(a, left, i - 1); // 最后用同样的方式对分出来的左边的小组进行同上的做法
    sort(a, i + 1, right); // 用同样的方式对分出来的右边的小组进行同上的做法
                           // 当然最后可能会出现很多分左右，知道每一组的i = j为止
}

#pragma mark 在主函数内部直接调用方法即可
int main(int argc, const char * argv[]) {
    @autoreleasepool {
        
        int a[10] = {0};
        for (int i = 0; i < 9; i ++) {
            a[i] = arc4random() % (100 - 50 + 1) + 50;
        }
        
        sort(a, 0, 10);
        for (int i = 0; i < 9; i ++) {
            NSLog(@"%d",a[i]);
        }
    }
    return 0;
}