快速排序（Quick Sort）的基本思想是：通過(guò)一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分姥闭，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序宵喂，以達(dá)到整個(gè)序列有序的目的蝌矛。
快速排序過(guò)程
基本思想
- 先從數(shù)列中取出一個(gè)數(shù)作為基準(zhǔn)數(shù)。
- 分區(qū)過(guò)程悬荣，將比這個(gè)數(shù)大的數(shù)全放到它的右邊菠秒，小于或等于它的數(shù)全放到它的左邊疙剑。
- 再對(duì)左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個(gè)數(shù)践叠。
C語(yǔ)言實(shí)現(xiàn)
QuickSort.h
#include <stdio.h>
void QuickSort(int *arr, int left, int right)
{
if (left < right)
{
int key = arr[left];
int low = left;
int high = right;
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;
QuickSort(arr, left, low - 1);
QuickSort(arr, low+1, right);
}
}
QuickSort_test.c
#include "QuickSort.h"
int main()
{
int i;
int arr[10] = {3, 5, 1, 4, 6, 8, 9, 7, 2, 0};
for (i = 0; i < 10; i++)
printf("%d ", arr[i]);
printf("\n");
QuickSort(arr, 0, 9);
for (i = 0; i < 10; i++)
printf("%d ", arr[i]);
getchar();
return 0;
}
