博客

• 快速排序算法在大多数计算机上运行都比其他排序算法快，而且快速排序算法在空间上只使用一个小的辅助栈，消耗的资源比其他的排序算法小，其内部的循环也很小。
• 快速排序的时间复杂度是O(nlogn），但是在极端情况下快速排序的时间复杂度会退化成O(n^2)。例如，如果数组中的数据原来已经是有序的了，比如1，3，5，6，8。如果我们每次选择最后一个元素作为pivot，那每次分区得到的两个区间 都是不均等的。我们需要进行大约n次分区操作，才能完成快排的整个过程。每次分区我们平均要扫描大约n/2个元素，这种情况下，快排的时间复杂度就 从O(nlogn)退化成了O(n^2)。
• 快速排序不是一种稳定的排序算法。对于排序码相同的元素，排序后可能会颠倒次序。

算法实现:

#include <stdlib.h>
#include <stdio.h>

void Sort(int sourceArr[], int startIndex, int endIndex)
{
	if(startIndex>=endIndex){//如果左边索引大于或者等于右边索引就代表已经整理完成一个组了
		return;
	}
	int i=startIndex;
	int j=endIndex;
	int key=sourceArr[startIndex];

	while(i<j){//控制在当组内寻找一遍
		while(i<j && key<=sourceArr[j]){
			j--;
		}
		sourceArr[i]=sourceArr[j];

		while(i<j && key>=sourceArr[i]){
			i++;
		}
		sourceArr[j]=sourceArr[i];
	}
	sourceArr[i]=key;//当在当组内找完一遍以后就把中间数key回归
	Sort(sourceArr, startIndex, i-1);
	Sort(sourceArr, i+1, endIndex);
}

int main(){
	int a[8] = {50, 10, 20, 30, 70, 40, 80, 60};
    int i, b[8];
    Sort(a, 0, 7);
    for(i=0; i<8; i++)
        printf("%d ", a[i]);
    printf("\n");
	return 0;
}

• 快速排序是一个效率很高的排序算法，但是对于长度很小的序列，快速排序算法的速度并不比一些简单的排序算法快，研究表明，序列长度M取值为5~25时，采用直接插入排序要比快速排序至少快10%。在快速排序算法的递归实现中程序多次因为小的序列而调用自身，因此对快速排序算法进行改进的一个简单方法:就是在递归调用过程，当待排序的子序列规模小于预先确定的M时，程序调用插入排序算法对此子序列进行排序。

void Sort(int sourceArr[], int startIndex, int endIndex)
{
    if(endIndex-startIndex<=M){
        InsertSort(sourceArr[], startIndex, endIndex);
    }else{
	       if(startIndex>=endIndex){//如果左边索引大于或者等于右边索引就代表已经整理完成一个组了
			return;
		}
		int i=startIndex;
		int j=endIndex;
		int key=sourceArr[startIndex];
	
		while(i<j){//控制在当组内寻找一遍
			while(i<j && key<=sourceArr[j]){
				j--;
			}
			sourceArr[i]=sourceArr[j];
	
			while(i<j && key>=sourceArr[i]){
				i++;
			}
			sourceArr[j]=sourceArr[i];
		}
		sourceArr[i]=key;//当在当组内找完一遍以后就把中间数key回归
		Sort(sourceArr, startIndex, i-1);
		Sort(sourceArr, i+1, endIndex);
    }
}

• 更为彻底的改进方法是：去基准对象pivot时采用在从序列左端点left、右端点right和中点位置mid=(left+right)/2中取中间值，并交换到right位置的方法，然后再对整个序列进行划分。

int median3(int sourceArr[], int startIndex, int endIndex){
    //此函数在表端、尾端和中间点三者取中值，交换到尾端
    int mid=(left+right)/2;
    int k=left;
    if(sourceArr[mid]<sourceArr[k])k=mid;
    if(sourceArr[right]<sourceArr[k])k=right;  //三者中选择最小，k指示
    if(k!=left) Swap(sourceArr[k],sourceArr[left]);//最小者交换到left
    if(mid!=right && sourceArr[mid]<sourceArr[right]) Swap(sourceArr[mid],sourceArr[right]);
      //sourceArr[mid]为中间值，交换到right的位置，否则right位置本来就是中间值
    return sourceArr[right];
}