C++ 快速排序算法实现 - 代码解析与实例

#include using namespace std;

// 交换函数 void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; }

// 分割函数 int partition(int arr[], int low, int high) { int pivot = arr[high]; // 以最后一个元素作为基准 int i = (low - 1); // 最小元素的索引

for (int j = low; j <= high - 1; j++) {
    // 如果当前元素小于或等于基准
    if (arr[j] <= pivot) {
        i++;    // 将最小元素的索引增加
        swap(&arr[i], &arr[j]);
    }
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);

}

// 快速排序函数 void quickSort(int arr[], int low, int high) { if (low < high) { // 找到分割点 int pi = partition(arr, low, high);

    // 分别对左右两部分进行递归排序
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
}

}

// 打印数组 void printArray(int arr[], int size) { for (int i = 0; i < size; i++) { cout << arr[i] << ' ';
} cout << endl; }

int main() { int arr[] = { 64, 34, 25, 12, 22, 11, 90 }; int n = sizeof(arr) / sizeof(arr[0]); cout << '原始数组：' << endl; printArray(arr, n);

quickSort(arr, 0, n - 1);

cout << '排序后的数组：' << endl;
printArray(arr, n);

return 0;

}