排序算法总结

一、主要排序算法由插入排序、中值排序、快速排序和堆排序四种
二、插入排序对小量数据并且初始数据几乎是有序的速度比较快，比如小于五个内容的数。但对大数据量的数据就比较差。
三、中值排序的平均情况为O(n log n),最坏情况为0(n的平方)的关键在于高效的从无序数组中选择出中值元素。中值排序退货成中枢值排序也就是快速排序

sort(A)
 medianSort(A,0,n-1)
end

medianSort(A,left,right)
if(left<right) then
 find median value A[me] in A[left,right]
 mid=(right+left)/2
 swap A[mid] and A[me]
 for i=left to mid-1 do
  if(A[i]>A[mid]) then
    find A[K] <= A[mid] where k>mid
    swap A[i] and A[k]
 medianSort(A,left,mid-1)
 medianSort(A,mid+1,right)
end

四、快速排序，平均情况O(n log n),最坏情况O(n平方)。在每一个递归步骤中把大小为n的数组都被切分成两个集合，如果其中一个集合为空，另外一个集合的大小为n-1,快速排序将退化成最坏的二次方行为。随机选择中枢值的算法使得快速排序在平均情况下表现的比其它排序算法要好。快递排序的各种优化
1、利用存储子任务的栈来消除递归
2、选择基于三中值分区中枢值
3、设定一个使用切分时数组长度的最小值，如果小于这个值，就使用插入排序。
4、当处理子数组的时候，首先将大的数组压入栈中，这样来最小化栈的总大小，确保小的问题首先被解决
选择中枢值的几种方式方法
1、选择第一个或最后一个
2、在A[left,left+n-1]中选择一个随机元素。
3、选择K中值，在A[left left+n-1]随便选择K个元素，然后选择这K个元素的中值班。

 sort(A)
  quickSort(A,0,n-1)
 end

quickSort(A,left,right)
 if(left<right) then
  pi=partition(A,left,right)
  quickSort(A,left,pi-1)
  quickSort(A,pi+1,right)
end

partition(A,left,right)
 p=select pivot in A[left,right]
 swap A[p] and A[right]
 store = left
 for i=left to right-1 do
  if(A[i]<=A[right] then
    swap A[i] and a[store]
    store++
 swap A[store] and A[right]
 return store
end