/*
数组：
    数组并不属于线性结构。数组是由类型相同的数据构成的有序集合 
    数组中的元素本身可以具有某种结构，而且元素的结构相同。数组
    中的元素可以是一个单一的元素，也可以是一个线性表，因此数组
    可以看做一般线性表的推广。 

寻找数组中第k小的数
    要查找第k小的数并不需要对整个数组进行排序，只需利用快速排序
    的思想，每次将数据分成两堆，只要中间参量的的位置为k就不需要
    再排序下去 
*/ 

/*
    快速排序
    快速排序是对冒泡排序的一种改进。基本思想是：通过一趟排序后将
    需要排序的数据分割成独立的两部分，其中一部分的所有数据都比另
    外一部分的所有数据都要小，然后再按照此方法对这两部分数据进行
    快速排序，整个排序过程可以递归进行，以此使整个数据都变成有序
    数据。 
*/

# include <stdio.h>
# define LEN 6

int find_k(int * arr, int low, int high, int k); 

int main(void)
{
    int arry[LEN] = {6, 2, 4, 1, 5, 9};
    int i;
    for (i = 0; i < LEN; ++i)
        printf("%-5d", arry[i]);
    printf("\n");
    int k;
    printf("请输入您需要查找的数的次序：k = ");
    scanf("%d", &k);
    int loc = find_k(arry, 0, LEN-1, k);
    printf("您查找的数为：%d\n", arry[loc]);
    
    return 0;
}

int find_k(int * arr, int low, int high, int k)
{
    int i, j;
    do
    {
        i = low; 
        j = high;
        int key;
        key = arr[low];
        while (low < high)   // 每次循环保证了将数据分成两部分，其中一部分所有数据都比另一部分所有数据小 
        {
            while (low < high && arr[high] >= key)
                --high;
            arr[low] = arr[high];
            while (low < high && arr[low] <= key)
                ++low;
            arr[high] = arr[low];
        }
        arr[low] = key;
        
        printf("low = %d, k = %d\n", low, k);
        for (int m = 0; m < LEN; ++m)
            printf("%-5d", arr[m]);
        printf("\n");
        
        // 把low作为比较位置 
        if (k == low+1)
        {
            break;
        }
        if (low+1 < k)  // 所要查找的数在low右边 
        {
            low = low + 1;
            high = j; 
        }
        else  // 所要查找的数在low左边 
        {
            high = low - 1;
            low = i; 
        }
    
    }while (low+1 != k);
    
    return low;
}