快速排序法 + 原地算法(泛型方法)

        private void Form1_Load(object sender, EventArgs e)
        {
            Random random = new Random();
            int count = 10;
            int[] array = new int[count];
            for (int i = 0; i < count; i++)
            {
                array[i] = random.Next(0, count);    // 亂數取得 0 ~ count-1 的任意值
            }

            //執行時間計算
            Stopwatch sw = new Stopwatch();
            sw.Start();

            //QucikSort1(array.ToList()).ToArray().CopyTo(array, 0);  //一千萬筆花了15秒左右
            QucikSort2(array, 0, array.Length - 1);                   //一千萬筆花了6秒左右

            sw.Stop();
            MessageBox.Show("總計花費的時間 ==> " + sw.Elapsed);
        }

        //快速排序法1
        public List<int> QucikSort1(List<int> list)
        {
            if (list.Count < 2)
                return list;

            int pivot = list[list.Count / 2];
            list.RemoveAt(list.Count / 2);
            List<int> less = new List<int>();
            List<int> greater = new List<int>();
            List<int> result = new List<int>();
            foreach (int n in list)
            {
                if (n > pivot)
                    greater.Add(n);
                else
                    less.Add(n);
            }
            result.AddRange(QucikSort1(less));
            result.Add(pivot);
            result.AddRange(QucikSort1(greater));
            return result;
        }

        //快速排序法2 (原地算法)
        public void QucikSort2(int[] array, int left, int right)
        {
            if (right <= left)
                return;

            int pivotIndex = (left + right) / 2;
            int pivot = array[pivotIndex];
            //Swap(array, pivotIndex, right);
            Swap<int>(array, pivotIndex, right);
            int swapIndex = left;
            for (int i = left; i < right; ++i)
            {
                if (array[i] <= pivot)
                {
                    //Swap(array, i, swapIndex);
                    Swap<int>(array, i, swapIndex);
                    ++swapIndex;
                }
            }
            //Swap(array, swapIndex, right);
            Swap<int>(array, swapIndex, right);

            QucikSort2(array, left, swapIndex - 1);
            QucikSort2(array, swapIndex + 1, right);
        }

        //原地算法（in-place algorithm）是一種使用小的，固定數量的額外之空間來轉換資料的算法
        private void Swap(int[] array, int indexA, int indexB)
        {
            int tmp = array[indexA];
            array[indexA] = array[indexB];
            array[indexB] = tmp;
        }

        //原地算法改用泛型方法
        private void Swap<T>(T[] array, int indexA, int indexB)
        {
            T tmp = array[indexA];
            array[indexA] = array[indexB];
            array[indexB] = tmp;
        }