思想：
選一個基準(zhǔn)值硕并， 將大于它的放右邊霎褐， 小于它的放左邊。找到該基準(zhǔn)值的下標(biāo)混移， 然后繼續(xù)遞歸調(diào)用祠墅。
代碼實現(xiàn)
// 快速排序
void quickSort(int a[], int n) {
if (n <= 1) {
return;
}
quickSort_c(a, 0, n - 1);
for (int i = 0; i < n; i++) {
NSLog(@"%d", a[i]);
}
}
// 遞歸函數(shù)
void quickSort_c(int a[], int left, int right) {
// 遞歸終止條件
if (left >= right) {
return;
}
// 找到分區(qū)下標(biāo)
int q = partionSection1(a, left, right);
// 遞歸調(diào)用
quickSort_c(a, left, q - 1);
quickSort_c(a, q + 1, right);
}
找到基準(zhǔn)值的下標(biāo)
分區(qū)實現(xiàn)一
int partionSection1(int a[], int left, int right) {
int i, j, pivot;
i = left;
// 取一個標(biāo)注數(shù)， 將小于它的放左邊歌径， 大于它的放右邊
pivot = a[right];
// 利用選擇排序思想
for (j = left; j <= right - 1; j++) {
if (a[j] < pivot) {
int temp = a[j];
a[j] = a[i];
a[i] = temp;
i = i + 1;
}
}
int tempR = a[i];
a[i] = a[right];
a[right] = tempR;
return i;
}
分區(qū)實現(xiàn)二
int partionSection2(int a[], int left, int right) {
int i = left;
int j = right;
int key = a[left]; // 基準(zhǔn)值
while (i < j) {
while (i < j && a[j] >= key) {
j--; // 左移
}
a[i] = a[j];
while (i < j && a[i] <= key) {
i++; // 右移
}
a[j] = a[i];
}
a[i] = key;
return i;
}
使用
int a[] = {4, 13, 2, 1, 7, 9, 10, 8, 3, 6};
int num = sizeof(a) / sizeof(int);
quickSort(a, num);
??細(xì)品分區(qū)一和分區(qū)二的實現(xiàn)
