class SortMehod    {   //-----快速排序----        private int Partition(List<int> array, int p, int r)        {            int x = array[r], temp;            int i = p - 1;         //类似于一个指示,在该指示左边的值均小于x            for (int j = p; j < r; j++)            {                if (array[j] <= x)    //遇到比x小的,放到i的下一位去                {                    i++;                    temp = array[i];                    array[i] = array[j];                    array[j] = temp;                }            }            array[r] = array[i + 1];            array[i + 1] = x;            return i + 1;        }        public void QuickSort(List<int> array, int p, int r)        {            int q;            if (p < r)  //进行递归的条件            {                q = Partition(array, p, r);                QuickSort(array, p, q - 1);                QuickSort(array, q + 1, r);            }        }        //-----归并排序----        private void Merge(List<int> array, int p, int q, int r)        {            int len1 = q - p + 1, n1 = 0;  //用于临时存储两边元素的数组的参数            int len2 = r - q, n2 = 0;            int[] arr1 = new int[len1];   //建立两个临时数组,用于储存数组值            int[] arr2 = new int[len2];            for (int i = 0; i < len1; i++)  //将array值拷贝到临时存放数组                arr1[i] = array[p + i];            for (int j = 0; j < len2; j++)                arr2[j] = array[j + q + 1];            for (int k = p; k < r + 1; k++)  //将两个数组中的值按升序放回到array数组中            {                if (arr1[n1]<arr2[n2])                    array[k] = arr1[n1++];                else                    array[k] = arr2[n2++];                if (n1 == len1)       //此处为arr1数组已全部取完后的处理情况                {                    for (int m = k + 1; m < r + 1; m++)                        array[m] = arr2[n2++];                    break;                }                if (n2 == len2)                {                    for (int m = k + 1; m < r + 1; m++)                        array[m] = arr1[n1++];                    break;                }            }        }        public void MergeSort(List<int> array, int p, int r)        {            if (p < r)            {                int q = (p + r) / 2;                MergeSort(array, p, q);                MergeSort(array, q + 1, r);                Merge(array, p, q, r);            }        }        //----插入排序-----        public void InsertSort(List<int> array)        {            for (int i = 1; i < array.Count; i++)   //将第i个数插入已排好序的[0...i-1]中            {                int key = array[i];                int position = i;  //用于记录将要插入的位置                for (int j = i; j >= 0; j--) //将要前面数与要插入数进行比较,如果比key大,往后移一位                {                    if (array[j] > key) //由于int实现了IComparable接口                    {                        array[j + 1] = array[j];                        position = j;                    }                }                array[position] = key;            }        }        //----堆排序----        private void MaxHeapify(List<int> array, int i, int length) //此处加个length是为了堆排序时取出最大下标        {            int largest = i;            int left = 2 * i + 1, right = 2 * i + 2;            if (left < length && array[left] > array[i]) //找出i,2i+1,2i+2中最大那个值的下标                largest = left;            if (right < length && array[right] > array[largest])                largest = right;            if (largest != i)            {                int temp = array[i];       //将最大值放入i中                array[i] = array[largest];                array[largest] = temp;                MaxHeapify(array, largest, length);   //将被改动那个下标再次递归进行维护            }        }        private void BuildMaxHeap(List<int> array)        {            for (int i = (array.Count - 2) / 2; i >= 0; i--) //此处i从(n-2)/2开始,因为没有子节点的节点无需进行"维护"                MaxHeapify(array, i, array.Count);        }        public void HeapSort(List<int> array)        {            BuildMaxHeap(array);            for (int i = array.Count - 1; i > 0; i--) //每次将堆得根与最大下标的值互换,并将最大下标"剔除"            {                int temp = array[i];                array[i] = array[0];                array[0] = temp;                MaxHeapify(array, 0, i);            }        }    }

    class Program    {        static void Main(string[] args)        {            int N = 100000;            Console.WriteLine("几种排序算法的性能比较:");            Random rnd=new Random();            SortMehod sort = new SortMehod();            Stopwatch sw = new Stopwatch();    //用于计时的代码            List<int> arr1 = new List<int>();            List<int> arr2 = new List<int>();            List<int> arr3 = new List<int>();            List<int> arr4 = new List<int>();            List<int> arr5 = new List<int>();            for(int i=0;i<N;i++)                arr1.Add(rnd.Next(0,N));            foreach(int a in arr1)            {                arr2.Add(a);                arr3.Add(a);                arr4.Add(a);                arr5.Add(a);            }                 Console.Write("归并排序耗时:    ");            sw.Reset();            sw.Start();            sort.MergeSort(arr2,0,arr2.Count-1);            sw.Stop();            TimeSpan ts = sw.Elapsed;            Console.Write("{0} ms", ts.TotalMilliseconds);            Console.WriteLine();            Console.Write("堆排序耗时:      ");            sw.Reset();            sw.Start();            sort.HeapSort(arr3);            sw.Stop();            ts = sw.Elapsed;            Console.Write("{0} ms", ts.TotalMilliseconds);            Console.WriteLine();            Console.Write("快速排序耗时:    ");            sw.Reset();            sw.Start();            sort.QuickSort(arr4,0,arr4.Count-1);            sw.Stop();            ts = sw.Elapsed;            Console.Write("{0} ms", ts.TotalMilliseconds);            Console.WriteLine();            Console.Write("自带排序耗时:    ");            sw.Reset();            sw.Start();            arr5.Sort();            sw.Stop();            ts = sw.Elapsed;            Console.Write("{0} ms", ts.TotalMilliseconds);            Console.WriteLine();            Console.Write("插入排序耗时:    ");            sw.Reset();            sw.Start();            sort.InsertSort(arr1);            sw.Stop();            ts = sw.Elapsed;            Console.Write("{0} ms", ts.TotalMilliseconds);            Console.WriteLine();            Console.ReadKey();        }    }