Go语言展现快速排序算法全过程的思路及代码示例
快速排序算法
快速排序是一个递归的思想，首先选择一个数作为基数，把数组中小于它的数放在它的左边，把大于它的数放在它的右边，然后对左右两边的数递归进行排序。
算法的关键部分是实现数组的划分，即怎么把数组的元素划分成两部分，使得左边的数比基数小，右边的数比基数大。划分有许多不同的实现方法，这里主要使用单向扫描的方法，后面再稍微介绍双向扫描的方法。
选择最右边的数字作为基数。使用一个变量j记录当前左边数字（比基数小的数）的最右的下标值。然后使用变量i从左到右遍历数组，如果a[i]比基数小，说明a[i]属于左边的数，就把j自增，然后交换a[j]和当前的a[i]。因为自增前的j是左边数字最右的下标，自增后的a[j]肯定不属于左边了，把其跟a[i]交换后，新的a[j]是属于左边的，而且此时j也重新变为左边数字最右的下标了。
扫描结束后，把j自增（因为a[j]将会被交换到最右边，因此要选属于右边的数字）后与最右边的基数交换，此时的j即为划分的结果。
Golang版的实现例子：
packagemain import"fmt" typeElemTypeint; funcmain(){ data:=make([]ElemType,600000)//ALLZERO variint=0; vardlenint=len(data); fori=0;i<dlen;i++{ data[i]=(ElemType)(dlen-i-1); } fmt.Println("Start...",len(data)); fori=0;i<100;i++{ fmt.Printf("%d",data[i]); } fmt.Println(); QuickSort(data,0,dlen-1); fmt.Println("End..."); fori=0;i<100;i++{ fmt.Printf("%d",data[i]); } fmt.Println(); } funcQuickSort(A[]ElemType,low,highint){ iflow<high{ //Partition()istheoperationofdivideA[low...high] //onetotwoarrayswhichcanbeusedasQuickSortAgain pivotpos:=Partition(A,low,high); QuickSort(A,low,pivotpos-1); QuickSort(A,pivotpos+1,high); } } funcPartition(A[]ElemType,low,highint) int{ varpivotElemType=A[low]; vartmpElemType; //MethodI: //forlow<high{ // forlow<high&&A[high]>=pivot{high--;} // A[low]=A[high]; // forlow<high&&A[low]<pivot{low++;} // A[high]=A[low]; //} //endofMI //MethodII: for(low<high)&&(A[high]>pivot){high--;} for(low<high)&&(A[low]<pivot){low++;} forlow<high{ //swapA[low]&A[high] tmp=A[low]; A[low]=A[high]; A[high]=tmp; low++; high--; } //endofMII A[low]=pivot; returnlow; }