//先上快排代码------------------------------------------------------------------------
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^)
新闻热点
疑难解答