快速排序是对冒泡排序的一种改进.
快速排序算法的基本思想是: 将所要进行排序的数分为左右两个部分, 其中一部分的所要数据都比另外一部分的数据小, 然后将所分得的两部分数据进行同样的划分, 重复执行以上划分操作, 知道所有要进行排序的数据变为有序数据为止.
代码
#include <stdio.h>
void patiton(int arr[], int low, int high) { //分别定义low和high为要进行排序的其实元素 和最后一个元素的下标, 第一次low和high的取值分别为0何n-1
int key; //定义key作为基准将数组分为左右两个部分
key = arr[low];
while(low < high) {
while(low<high && arr[high] >= key)
high--;
if(low < high)
arr[low++] = arr[high];
while(low < high && arr[low] <= key)
low++;
if(low < high)
arr[high--] = arr[low];
}
arr[low] = key;
return low;
}
void quick_sort(int arr[], int start, int end) {
int pos;
if(start < end) {
pos = partition(arr, start, end);
quick_sort(arr, start,pos-1);
quick_sort(arr,pos+1,end);
}
return;
}
int main () {
int arr[] = {32, 12, 8, 76, 21, 17, 24, 49, 78, 3};
quick_sort(arr, 0, 9);
for(int i= 0; i < 10; i++)
printf("%d ", arr[i]);
}
运行结果:
性能
快速排序的时间复杂度为O(NlogN, 空间复杂度为O(logN), 但最坏情况下, 时间复杂度为O(N^2), 空间复杂度为O(N); 且排序是不稳定的, 但每次都能确定一个元素所在序列中的最终位置, 复杂度和初始序列有关.
==~ end ~==