C语言实现交换排序——快速排序

C语言实现快速排序

文章目录

快速排序算法

1.划分操作

//划分操作
int Partition(int arr[], int low, int high) {		//一趟划分int point = arr[low];							//将当前表中的第一个元素设为基准点，对表进行划分while (low < high) {while (low < high && arr[high] >= point)	//循环跳出条件high--;arr[low] = arr[high];						//将比基准小的元素移到左端while (low < high && arr[low] <= point)low++;arr[high] = arr[low];						//将比基准大的元素移到右端}arr[low] = point;								//基准元素存放到最终位置return low;
}

2.快速排序算法实现

//快速排序算法
void QuickSort(int arr[], int low, int high) {int point;      //基准点if (low < high) {								//递归跳出条件//将表arr[low…high]划分为两个子表point = Partition(arr, low, high);			//划分QuickSort(arr, low, point - 1);				//依次对两个子表进行递归排序QuickSort(arr, point + 1, high);}
}

项目完整代码

//交换排序————快速排序（不稳定，空间效率最好情况O(logn)，最坏O(n)；时间效率最好情况O(nlogn)，最坏O(n^2)）
//快速排序的平均时间效率接近最好情况O(nlogn)，是所有内部排序中平均性能最优的排序算法
#include <stdio.h>//划分操作
int Partition(int arr[], int low, int high) {		//一趟划分int point = arr[low];							//将当前表中的第一个元素设为基准点，对表进行划分while (low < high) {while (low < high && arr[high] >= point)	//循环跳出条件high--;arr[low] = arr[high];						//将比基准小的元素移到左端while (low < high && arr[low] <= point)low++;arr[high] = arr[low];						//将比基准大的元素移到右端}arr[low] = point;								//基准元素存放到最终位置return low;
}//快速排序算法
void QuickSort(int arr[], int low, int high) {int point;      //基准点if (low < high) {								//递归跳出条件//将表arr[low…high]划分为两个子表point = Partition(arr, low, high);			//划分QuickSort(arr, low, point - 1);				//依次对两个子表进行递归排序QuickSort(arr, point + 1, high);}
}int main() {int arr[] = {49, 38, 65, 97, 76, 13, 27, 49};int len = sizeof(arr) / sizeof(int);//快速排序QuickSort(arr, 0, len - 1);//将已排序结果输出printf("快速排序结果为：");for (int i = 0; i < len; ++i) {printf("%d ", arr[i]);}return 0;
}

运行效果图

    int arr[] = {49, 38, 65, 97, 76, 13, 27, 49};