在前面的排序中所描述的算法。最快的排序算法是归并排序,但是有一个缺陷合并排序排序过程的需求O(N)额外的空间。本文介绍了高速的排序算法到位排序算法,所需的复杂性的额外空间O(1)。
算法介绍:高速排序事实上一种依据需找某个元素的详细位置进行排序的方法。比方所存在例如以下数组
选择第一个元素5。找到5终于的位置。即5的左边的数都小于或者等于5。右边的数都大于或者等于5.
从"6"開始,可知6大于5,此处停住。从“2”開始2小于5,因此交换6与2的位置。然后接着往下走,将全部小于等于5的都放在左边,大于等于5的都放在右边,等到例如以下所看到的的数组:
此时的索引在4的位置,然后交换5和4的位置,这样就保证了左边的都小于5。右边的都大于5。
然后再分别对5的左右两边反复上述过程就可以将数组按升序排列。
算法发复杂度分析:如果每次都从中间将数组分开,且算法的执行时间为T(N)。则根据算法的执行过程可知。找到当前元素的位置须要扫面一遍数组即N次,然后再对此元素两边的子数组反复上述操作。
为此T(N)=2*T(N/2)+N,解得T(N)=O(NlogN)。
算法实现:
寻找切分点
int sort::partition(int* a, const int low, const int high) { int value = a[low]; int i=low; int j=high+1; while (1) { while(a[++i] < value) { if(i == high) break; } while(value < a[--j]); //a[low] == value,因此能够知道j==low时。此推断条件不成立,可知此时i必大于j,从而整个循环结束。 if(i>=j) break; swap(a,i,j); } swap(a,low,j); return j; }
高速排序:
void sort::quick_sort(int* a, const int low, const int high) { if(low >= high) return; int loc = partition(a,low,high); quick_sort(a,low,loc-1); quick_sort(a,loc+1,high); }
上述即为高速排序的详细实现。可是对上述算法还有非常多的改进之处。比方说对存在大多数反复数据的数组排序,初始切分点的选取等等都能够进行改进。详细的改进例如以下所看到的:
对于较小的子数组使用插入排序:
void sort::insert_sort_update(int* a, const int n) { for(int i=1; i<n; i++) { int j=i; int temp = a[i]; for(; j>0 && temp < a[j-1]; j--) { a[j] = a[j-1]; } a[j] = temp; } } void sort::quick_sort_update_with_insert_sort(int* a, const int low, const int high) { if(high <= low+N) { insert_sort_for_update(a,low,high); return; } int loc = partition(a,low,high); quick_sort_update_with_insert_sort(a,low,loc-1); quick_sort_update_with_insert_sort(a,loc+1,high); }
对于含有大多数反复元素的改进:
void sort::quick_sort_update_with_partition(int* a,const int low, const int high) { if(low>=high) return; int lt = low; int gt = high; int value = a[low]; int i=low+1; while(i<=gt) { if(a[i]<value) { swap(a,i,lt); i++; lt++; } else if(a[i] > value) { swap(a,i,gt); gt--; } else { i++; } } quick_sort_update_with_partition(a,low,lt-1); quick_sort_update_with_partition(a,gt+1,high); }
他说,博文介绍了高速的排序算法和改进。欢迎拍砖
版权声明:本文博客原创文章,博客,未经同意,不得转载。