随机快排思想实现查找第k顺序统计量

• 1 代码
• • 1.1 第k顺序统计量
  • 1.2 划分函数
  • 1.3 交换函数
• 2 测试例程
• • 打印被测数组

1 代码

1.1 第k顺序统计量

int OrderStatistics(int *arr, int start, int end, int order)
{// k-th order statistics
    int r = 0;

    if(start == end){ // Only 1 element in the array
        return arr[start];
    }

    r = partition(arr, start, end);
    if(r == order){
        return arr[r];
    }else if(order < r){
        return OrderStatistics(arr, start, r - 1, order);
    }else{
        return OrderStatistics(arr, r + 1, end, order);
    }
}

1.2 划分函数

int partition(int *arr, int start, int end)
{
    int midValue;
    int i = start;
    int j = start + 1;

    srand(time(NULL));
    int random = start + rand() % (end - start + 1);
    // printf("start is %d; end is %d; random is %d\r\n", start, end, random);
    swap(&arr[start], &arr[random]);

    midValue = arr[start];

    for( ;j <= end; j++){
        if(arr[j] <= midValue){
            i++;
            swap(&arr[i], &arr[j]);
        }
    }

    swap(&arr[start], &arr[i]);

    return i;
}

1.3 交换函数

void swap(int *ip1, int *ip2)
{
    int temp = 0;
    temp = *ip1;
    *ip1 = *ip2;
    *ip2 = temp;
}

2 测试例程

int test[] = {5, 1, 5, 3, 4, 6, 7, 8, 9, 5};

int main(int argc, char *argv[])
{
    test_printf(test, sizeof(test) / sizeof(int));
    int order = 10; // index from 1 to ...
    int orderNum = OrderStatistics(test, 0, sizeof(test) / sizeof(int) - 1, order - 1);
    printf("order %d number is %d\r\n", order, orderNum);
    return 0;
}

打印被测数组

void test_printf(int *arr, int len)
{
    int i = 0;
    for( ; i < len; i++){
        printf("|%6d", test[i]);
        if((i+1) % 8 == 0){
            printf("|\r\n");
        }
    }
    if(i%8 != 0){
        printf("|\r\n");
    }
}