下面給出C語言實現快速排序算法的代碼:
#include <stdio.h>
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
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++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = { 7, 2, 1, 6, 8, 5, 3, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array:\n");
printArray(arr, n);
quickSort(arr, 0, n - 1);
printf("Sorted array:\n");
printArray(arr, n);
return 0;
}
快速排序是一種常用且高效的排序算法,通過選擇一個基準元素,將小于基準元素的數都放到基準元素的左邊,將大于基準元素的數都放到基準元素的右邊,然后按照同樣的方法遞歸地對左右兩個子序列進行排序,直到整個序列有序。
以上代碼中,swap
函數用于交換兩個元素的值,partition
函數用于找到基準元素的正確位置并將數組劃分為兩部分,quickSort
函數用于遞歸地對左右兩個子序列進行排序,printArray
函數用于打印數組。
在 main
函數中,首先定義了一個待排序的數組 arr
,然后調用 quickSort
函數進行排序,最后調用 printArray
函數打印排序后的數組。