快速排序

快速排序

原理：欧几里德算法
快排的概念：分而治之

代码：

void display(int array[], int maxlen)
{
    int i;
    
    for(i = 0; i < maxlen; i++)
    {
        printf("%-3d", array[i]);
    }
    printf("\n");
    
    return ;
}

void swap(int *a, int *b)
{
    int temp;
    
    temp = *a;
    *a = *b;
    *b = temp;
    
    return ;
}

void quicksort(int array[], int maxlen, int begin, int end)
{
    int i, j;
    
    if(begin < end)
    {
        i = begin + 1;  // 将array[begin]作为基准数，因此从array[begin+1]开始与基准数比较！
        j = end;        // array[end]是数组的最后一位
        
        while(i < j)
        {
            if(array[i] > array[begin])  // 如果比较的数组元素大于基准数，则交换位置。
            {
                swap(&array[i], &array[j]);  // 交换两个数
                j--;
            }
            else
            {
                i++;  // 将数组向后移一位，继续与基准数比较。
            }
        }
        
        /* 跳出while循环后，i = j。
         * 此时数组被分割成两个部分  -->  array[begin+1] ~ array[i-1] < array[begin]
         *                           -->  array[i+1] ~ array[end] > array[begin]
         * 这个时候将数组array分成两个部分，再将array[i]与array[begin]进行比较，决定array[i]的位置。
         * 最后将array[i]与array[begin]交换，进行两个分割部分的排序！以此类推，直到最后i = j不满足条件就退出！
         */
        
        if(array[i] >= array[begin])  // 这里必须要取等“>=”，否则数组元素由相同的值时，会出现错误！
        {
            i--;
        }
        
        swap(&array[begin], &array[i]);  // 交换array[i]与array[begin]
        
        quicksort(array, maxlen, begin, i);
        quicksort(array, maxlen, j, end);
    }
}


// 快速排序

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        // insert code here...
        int a[] = {0,1,23,134,5435,654645,24,2222,10,12,19,33,90};
        int max = sizeof(a) / sizeof(int);
        quicksort(a, max, 0, max - 1);
        display(a, max);
    }
    return 0;
}