C#快速排序法（两种方法。第一种通俗易懂，第二种效率高）

C#快速排序法（两种方法。第一种通俗易懂，第二种效率高）

using System;using System.Collections.Generic;using System.Text;using System.Diagnostics;namespace QSort{class Program{static void Main(string[] args){int n = 9999999;//更改数组的大小Random r=new Random();int[] arr =new int[n];//声明一个数组for (int i = 0; i < arr.Length; i++){arr[i] = r.Next(n+500);}List<int> list = new List<int>(arr);//将数组添加到list集合中Stopwatch st1 = new Stopwatch();//计时器用来计算算法要用多久时间st1.Start();QuickSort(list);st1.Stop();//遍历数组检测排序是否正确//foreach (object i in list)//{//    Console.Write(i+\" \");//}Console.WriteLine(\"========================================\");Stopwatch st2 = new Stopwatch();st2.Start();QuickSort2(arr,0,arr.Length-1);st2.Stop();//遍历数组检测排序是否正确//foreach (object i in list)//{//    Console.Write(i + \" \");//}Console.WriteLine();Console.WriteLine(\"一共 \"+n+\" 个数\");Console.WriteLine(\"第一个方法运行时间：\" + st1.Elapsed);Console.WriteLine(\"第二个方法运行时间：\" + st2.Elapsed);Console.ReadKey();}/*第一种方法：用List集合次方通俗易懂，* 但在数组成员多了以后会比第二种计算* 速度慢* 应该也会比较耗资源因为他要创建新的List集合；*/public static void QuickSort(List<int> list){if (list.Count > 1){List<int> smaller = new List<int>();//比基准值小的List<int> same = new List<int>();//同样大List<int> larger = new List<int>();//比基准值大的int pivot = list[0];//基准值//分类foreach (int i in list){if (i < pivot)smaller.Add(i);else if (i > pivot)larger.Add(i);elsesame.Add(i);}//对大、小数组继续调用递归QuickSort(smaller);QuickSort(larger);list.Clear();list.AddRange(smaller);list.AddRange(same);list.AddRange(larger);}}/*第二种方法：用数组计算，此方法无需生成新的数组，* 而是人为的将一个数组划分两个区域.* 数组大了之后计算速度比较快*///将一个数组看为两个，第一个小数组起点为原数组的起点//第二个大数组起点为原数组的终点public static void QuickSort2(int[] list, int left, int right){if (left >= right)//若数组的左端下标大于或等于右端下标，则表明数组为一或空{return;//结束方法}int i, j, temp;i = left;j = right;temp = list[left];//将数组中的第一个元素当做基准值while (i != j)//当i=j时，表明将大于基准值的数和小于基准值的数全部分开{while (list[j] >= temp && i < j){j--;}while (list[i] <= temp && i < j){i++;}//交换数组中大于基准值的数和小于基准值的数if (i < j){int t = list[i];list[i] = list[j];list[j] = t;}}//将基准值放到大数组和小数组中间list[left] = list[i];list[i] = temp;QuickSort2(list, i + 1, right);QuickSort2(list, left, i - 1);}}}