快速排序c语言实现 快速排序——C语言实现

void exchange(int* x, int* y)

{

int temp = *x;

*x = *y;

*y = temp;

}

// 快速排序是一种原址排序，不需要分配新的数组空间

// start和end为子数组的起始位置与终止位置

int partition(int *arr, int start, int end)

{

int temp;

// 获取主元

int key = arr[end];

// left不存在，故将i去值为start-1

int i = start - 1;

for (int j = start; j < end; j++)

{

if (arr[j] <= key)

{

i = i + 1;

exchange(arr + i, arr + j);

}

}

exchange(arr + i + 1, arr + end);

return i + 1;

}

void quickSort(int *arr, int start, int end)

{

if (start < end)

{

int mid = partition(arr, start, end);

quickSort(arr, start, mid - 1);

quickSort(arr, mid + 1, end);

}

}

图片是从算法导论截取的。个人觉得看懂上面这两幅图，就理解了快排的思路。

上面这两张图是数组分割的过程，整个快速排序就是数组分割，然后在子数组上继续递归调用快排。

下面是分割以及快排的伪代码，for循环中的to表示小于等于partition(A, start, end)

key = A[end]

i = start - 1

for j = start to end - 1

if A[j] <= key

i = i + 1

exchange A[i] with A[j]

exchange A[i+1] with A[j]

quickSort(A, start, end)

if start < end

mid = partition(A, start, end)

quickSort(A, start, mid - 1)

quickSort(A, mid + 1, end)