|
快速交换排序（Quick Exchange Sort） 快速交换排序是由图灵奖获得者Tony Hoare（东尼.霍尔）所发展的一种排序算法，是采用分治策略的一个非常典型的应用。快速交换排序虽然高端，但其思想是来自冒泡交换排序的，冒泡交换排序是通过相邻元素的比较和交换把最小的冒泡到最顶端，而快速交换排序是比较和交换小数和大数，这样一来不仅小数冒泡到上面的同时也把大数沉到下面。其基本思想如下： （1）选择一个基准元素，通常选择第一个元素或者最后一个元素。 （2）通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的元素值比基准值大。 （3）此时基准元素在其排好序的正确位置。 （4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。 即：从待排记录中选一记录，将其放入正确的位置，然后以该位置为界，对左右两部分再做快速排序，直到划分的长度为1。 如：int[] Key = new int[]{45,34,78,12,34,32,29,64}; private static void QuickSort<T>(T[]array, int left, int right) where T : IComparable<T> { //快速排序递归函数 if(left < right) { T current = array[left]; int i = left; int j = right; while(i < j) { while(array[j].CompareTo(current) > 0 && i < j) j--; while(array[i].CompareTo(current) <= 0 && i < j) i++; if(i < j) { T temp = array[i]; array[i] = array[j]; array[j] = temp; j--; i++; } } array[left] = array[j]; array[j] = current; if(left < j - 1) QuickSort(array, left, j - 1); if(right > j + 1) QuickSort(array, j + 1, right); } } ///<summary> ///快速交换排序 ///</summary> ///<typeparamname="T">需要排序记录的类型</typeparam> ///<paramname="array">需要排序的记录集合</param> public stati cvoid QuickExchangeSort<T>(T[] array) where T : IComparable<T> { QuickSort(array, 0, array.Length - 1); } 其实上面的代码还可以再优化，上面代码中基准元素已经在current中保存了，所以不需要每次交换都设置一个temp变量，在交换的时候只需要先后覆盖就可以了。这样既能较少空间的使用还能降低赋值运算的次数。优化代码如下： private static void QuickSortImproved<T>(T[] array, int left, int right) whereT : IComparable<T> { //快速排序递归函数 if(left < right) { T current = array[left]; int i = left; int j = right; while(i < j) { while(array[j].CompareTo(current) > 0 && i < j) j--; array[i] = array[j]; while(array[i].CompareTo(current) <= 0 && i < j) i++; array[j] = array[i]; } array[j] = current; if (left< j - 1) QuickSortImproved (array, left, j - 1); if(right > j + 1) QuickSortImproved (array, j + 1, right); } } ///<summary> ///快速交换排序 ///</summary> ///<typeparamname="T">需要排序记录的类型</typeparam> ///<paramname="array">需要排序的记录集合</param> public static void QuickExchangeSortImproved<T>(T[] array) whereT : IComparable<T> { QuickSortImproved(array, 0, array.Length - 1); } 华北电力大学LSGO软件技术团队成立于2010年09月25日，团队主要以机器学习和地理信息系统为主要研究方向，成立几年来为学校培养了大量优秀人才，他们或者就职于IBM、阿里巴巴、网易游戏、百度等IT企业，或者就读于中科院信安所、中科院计算所、中科院自动化所、中国科技大学、北京理工大学、武汉大学、华南理工大学、哈尔滨工业大学、华北电力大学等著名高校。 今年（2016年07月）毕业的李文乔同学保送到北京理工大学，安晟同学继续在华北电力大学读研究生，期间华硕公司，小米公司也希望团队推荐学生就业，综上，来LSGO软件技术团队学习可作为驻保高校学生，打发课余时间的一个不错选择。 如果对我们感兴趣，可以与我联系，通过考核后即可成为我们的一员。 请阅读以下代码（C#），得到联系方式： |
|
|
