排序数组-快速排序和归并排序

快速排序类似二叉树的前序遍历，归并排序类似二叉树的后序遍历。

Leetcode 912._排序数组

1、快速排序

        public int[] SortArray(int[] nums)
        {
            Quick(nums, 0, nums.Length - 1);
            return nums;
        }
        void Quick(int[] nums, int left, int right)
        {
            if(left < right)
            {
                int index = QuickSort(nums, left, right);
                Quick(nums, left, index - 1);
                Quick(nums, index+1, right);
            }
        }
        int QuickSort(int[] nums,int left,int right)
        {
            int pviot = nums[left];
            while (left < right) 
            {
                while (left < right && nums[right] >= pviot) 
                    right--;
                if(left < right) nums[left] = nums[right];
                while (left < right && nums[left] <= pviot)
                    left++;
                if (left < right) nums[right] = nums[left];
            }
            nums[left] = pviot;
            return left;
        }

2、归并排序

        int[] temp;
        public int[] SortArray(int[] nums)
        {
            temp = new int[nums.Length];
            Sort(nums, 0, nums.Length - 1);
            return nums;
        }
        void Sort(int[] nums,int left,int right)
        {
            if (left == right) return;
            int mid = left + (right - left) / 2;
            Sort(nums, left, mid);
            Sort(nums, mid+1, right);
            Merge(nums,left,mid,right);
        }
        void Merge(int[] nums,int left,int mid,int right)
        {
            for (int x = left; x <= right; x++)
                temp[x] = nums[x];
            int i = left, j = mid + 1;
            for (int y = left; y <= right; y++)
            {
                if (i == mid + 1)
                    nums[y] = temp[j++];
                else if (j == right + 1)
                    nums[y] = temp[i++];
                else if (temp[i] > temp[j]) 
                    nums[y] = temp[j++];  
                else
                    nums[y] = temp[i++];
            }
        }