c# 快速排序 归并排序

快速排序 （重要）

分治、递归
时间复杂度O(Nlog N) ， N是数组的长度

        public int[] SortArray(int[] nums)
        {
            QuickSort(nums, 0, nums.Length - 1);
            return nums;
        }

        public void QuickSort(int[] array, int begin, int end)
        {
            if (end <= begin) return;
            int pivot = partition(array, begin, end);
            QuickSort(array, begin, pivot - 1);
            QuickSort(array, pivot + 1, end);
        }

        private int partition(int[] array, int begin, int end)
        {
            int pivot = end;//标杆位置
            int counter = begin;//小于pivot的元素的个数
            for (int i = begin; i < end; i++)
            {
                if (array[i] < array[pivot])
                {
                    int temp = array[counter]; array[counter] = array[i]; array[i] = temp;
                    counter++;
                }
            }
            int temp2 = array[pivot]; array[pivot] = array[counter]; array[counter] = temp2;
            return counter;
        }

归并排序 （重要）

时间复杂度O(Nlog N)

        public int[] SortArray(int[] nums)
        {
            MergeSort(nums, 0, nums.Length - 1);
            return nums;
        }

        public void MergeSort(int[] array, int left, int right)
        {
            if (right <= left) return;
            int mid = (left + right) / 2;//(left+right)/2

            MergeSort(array, left, mid);
            MergeSort(array, mid + 1, right);

            int[] temp = new int[right - left + 1];//中间数组
            int i = left, j = mid + 1, k = 0;
            while (i <= mid && j <= right)
            {
                temp[k++] = array[i] <= array[j] ? array[i++] : array[j++];
            }
            while (i <= mid) temp[k++] = array[i++];
            while (j <= right) temp[k++] = array[j++];
            for (int p = 0; p < temp.Length; p++)
            {
                array[left + p] = temp[p];
            }
        }