你的位置:首页 > ASP.net教程

[ASP.net教程]C#写快速排序


//先上快排代码------------------------------------------------------------------------
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^)