//先上快排代碼------------------------------------------------------------------------
public static void QuickSort(int leftIndex, int rightIndex, int[] arrayNeedSort) { int i, j, t, temp; if (leftIndex > rightIndex) { return; } temp = arrayNeedSort[leftIndex];//基準數 i = leftIndex; j = rightIndex; while (i != j) //如果左側索引和右側索引不想等 { while (arrayNeedSort[j] >= temp && i < j) //右側索引先行 從右側找到第一個比基準數temp小的 到此索引位置停下來 { j--; //如果說大于等于 基準數temp 則往左走 也就是索引j-1 } while (arrayNeedSort[i] <= temp && i < j) //左側索引后行 從左側找到比基準數大的 到此索引停下來 { i++; //如果說小于等于temp基準數的情況 索引繼續向右走 i+1 } if (i < j) { t = arrayNeedSort[i]; //交換左右索引位置的數據 也就是說交換左側大于temp的第一個索引 右側小于temp的第一個索引的數據 arrayNeedSort[i] = arrayNeedSort[j]; arrayNeedSort[j] = t; } } //基準數歸位(跳出前面i!=j的循環,就是i=j相遇的情況,如果相遇,那就把基準數的位置和 相遇點的索引位置的索引交換) arrayNeedSort[leftIndex] = arrayNeedSort[i]; arrayNeedSort[i] = temp; QuickSort(leftIndex, i - 1, arrayNeedSort); //繼續處理剛剛歸位的左側的數組的排序 QuickSort(i + 1, rightIndex, arrayNeedSort); //繼續處理剛剛歸位的基準數的右側的數組排序 遞歸的過程 }
調用快排方法
int[] arrayNeedSort = new[] { 6, 2, 3, 9, 6, 54, 9, 34, 7, 3, 0, 6, 4, 2, 9, 8, 1, 3 }; int i; int arrayLength = arrayNeedSort.Length; QuickSort(0, arrayLength-1, arrayNeedSort); foreach (var item in arrayNeedSort) { Console.WriteLine(item); } Console.ReadKey();
輸出結果
快排的平均時間復雜度O(NlogN).在最壞的情況下,和冒泡排序一樣都是O(N^)
新聞熱點
疑難解答