学习日志(十二)

函数递归-快速排序

快速排序

算法的核心思想是挑出一个元素作为基准。

快速排序的步骤

(1）从数列中挑出一个元素，称为 "基准"(pivot);

(2）重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

(3）递归地把小于基准值元素的子数列和大于基准值元素的子数列排序；

#include <stdio.h>

/／交换算法 通过指针交换两个数

void swap(int* x, int* y) {

int t = *x;

*x = *y;

*y = t;

}

void QuickSortRecursive(

int arr[], int start)

if (start ≥ end)

return;

int mid=arr[end];

int left = start, right = end - 1;

while (left < right) {

while (arr[left] < mid && left < right)

left++;

while (arr[right] ≥ mid && left<right

right--;

swap(&arr[left],&arr[right]);

if[arr[left]≥arr[end]]

swap(&arr[left],&arr[end]);

else

left++;

if (left)

QuickSortRecursive(arr, start, left - 1)

QuickSortRecursive(arr, left + 1,end);

}

void QuickSort(int arr[], int len){

QuickSortRecursive(arr, 0, len - 1);

int main()

/／需要归并排序的数组

int arr[]= { 1,1,4,5,1,4,19,19,810 };

/／传入数组arr的首地址进行排序

QuickSort(arr,sizeof(arr)/ sizeof(int));

/／排序完成后顺序输出排序结束后的arr数组

for (int i = 0; i ≤ 9; i++) {

printf("%d",arr[i]);

}

return 0;

}