class SortAlgorithm
    {
        static void Main(string[] args)
        {
            int[] arr1 = { 1, 4, 2, 7, 9, 8, 3, 6 };
            //ShellSort(arr1);
            //DirectInsertSort(arr1);
            //BubbleSort(arr1);
            //QuickSort(arr1, 0, arr1.Length - 1);
            //SimpleSelectSort(arr1);
            //MergeSort(arr1);
            //HeapSort(arr1);
            Console.Read();
        }

        public static void DirectInsertSort(int[] arr)
        {
            for (int i = 1; i < arr.Length; i++)
            {
                if (arr[i] < arr[i - 1])
                {//注意[0,i-1]都是有序的。如果待插入元素比arr[i-1]还大则无需再与[i-1]前面的元素进行比较了，反之则进入if语句
                    int temp = arr[i];
                    int j;
                    for (j = i - 1; j >= 0 && arr[j] > temp; j--)
                    {
                        arr[j + 1] = arr[j];//把比temp大或相等的元素全部往后移动一个位置            
                    }
                    arr[j + 1] = temp;//把待排序的元素temp插入腾出位置的(j+1)
                }
            }
        }

        public static void ShellSort(int[] arr)
        {
            //增量gap，并逐步缩小增量
            for (int gap = arr.Length / 2; gap > 0; gap /= 2)
            {
                //从第gap个元素，逐个对其所在组进行直接插入排序操作
                for (int i = gap; i < arr.Length; i++)
                {
                    int j = i;
                    int temp = arr[j];
                    if (arr[j] < arr[j - gap])
                    {
                        while (j - gap >= 0 && temp < arr[j - gap])
                        {
                            //移动法
                            //arr[j] = arr[j - gap];
                            //插入排序采用交换法
                            swap(arr, j, j - gap);

                            j -= gap;
                        }
                        arr[j] = temp;
                    }
                }
            }
        }

        public static void swap(int[] arr, int a, int b)
        {
            arr[a] = arr[a] + arr[b];
            arr[b] = arr[a] - arr[b];
            arr[a] = arr[a] - arr[b];
        }

        public static void BubbleSort(int[] R)
        {
            for (int i = 0; i < R.Length; i++)
            {
                for (int j = 0; j < R.Length - i - 1; j++)
                {
                    if (R[j] > R[j + 1])
                    {
                        swap(R, j, j + 1);
                    }
                }
            }
        }

        public static void SimpleSelectSort(int[] arr)
        {
            for (int i = 0; i < arr.Length - 1; i++)
            {
                int min = i;//每一趟循环比较时，min用于存放较小元素的数组下标，这样当前批次比较完毕最终存放的就是此趟内最小的元素的下标，避免每次遇到较小元素都要进行交换。
                for (int j = i + 1; j < arr.Length; j++)
                {
                    if (arr[j] < arr[min])
                    {
                        min = j;
                    }
                }
                //进行交换，如果min发生变化，则进行交换
                if (min != i)
                {
                    swap(arr, min, i);
                }
            }
        }

        public static void QuickSort(int[] arr, int _left, int _right)
        {
            int left = _left;
            int right = _right;
            int temp = 0;
            if (left <= right)
            {   //待排序的元素至少有两个的情况
                temp = arr[left];  //待排序的第一个元素作为基准元素
                while (left != right)
                {   //从左右两边交替扫描，直到left = right

                    while (right > left && arr[right] >= temp)
                        right--;        //从右往左扫描，找到第一个比基准元素小的元素
                    arr[left] = arr[right];  //找到这种元素arr[right]后与arr[left]交换

                    while (left < right && arr[left] <= temp)
                        left++;         //从左往右扫描，找到第一个比基准元素大的元素
                    arr[right] = arr[left];  //找到这种元素arr[left]后，与arr[right]交换
                }
                arr[right] = temp;    //基准元素归位
                QuickSort(arr, _left, left - 1);  //对基准元素左边的元素进行递归排序
                QuickSort(arr, right + 1, _right);  //对基准元素右边的进行递归排序
            }
        }

        public static void MergeSort(int[] arr)
        {
            int[] temp = new int[arr.Length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
            MergeSort(arr, 0, arr.Length - 1, temp);
        }
        private static void MergeSort(int[] arr, int left, int right, int[] temp)
        {
            if (left < right)
            {
                int mid = (left + right) / 2;
                MergeSort(arr, left, mid, temp);//左边归并排序，使得左子序列有序
                MergeSort(arr, mid + 1, right, temp);//右边归并排序，使得右子序列有序
                merge(arr, left, mid, right, temp);//将两个有序子数组合并操作
            }
        }
        private static void merge(int[] arr, int left, int mid, int right, int[] temp)
        {
            int i = left;//左序列指针
            int j = mid + 1;//右序列指针
            int t = 0;//临时数组指针
            while (i <= mid && j <= right)
            {
                if (arr[i] <= arr[j])
                {
                    temp[t++] = arr[i++];
                }
                else
                {
                    temp[t++] = arr[j++];
                }
            }
            while (i <= mid)
            {//将左边剩余元素填充进temp中
                temp[t++] = arr[i++];
            }
            while (j <= right)
            {//将右序列剩余元素填充进temp中
                temp[t++] = arr[j++];
            }
            t = 0;
            //将temp中的元素全部拷贝到原数组中
            while (left <= right)
            {
                arr[left++] = temp[t++];
            }
        }

        public static void HeapSort(int[] arr)
        {
            //1.构建大顶堆
            for (int i = arr.Length / 2 - 1; i >= 0; i--)
            {
                //从第一个非叶子结点从下至上，从右至左调整结构
                adjustHeap(arr, i, arr.Length);
            }
            //2.调整堆结构+交换堆顶元素与末尾元素
            for (int j = arr.Length - 1; j > 0; j--)
            {
                swap(arr, 0, j);//将堆顶元素与末尾元素进行交换
                adjustHeap(arr, 0, j);//重新对堆进行调整
            }

        }

        /**
         * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
         * @param arr
         * @param i
         * @param length
         */
        public static void adjustHeap(int[] arr, int i, int length)
        {
            int temp = arr[i];//先取出当前元素i
            for (int k = i * 2 + 1; k < length; k = k * 2 + 1)
            {//从i结点的左子结点开始，也就是2i+1处开始
                if (k + 1 < length && arr[k] < arr[k + 1])
                {//如果左子结点小于右子结点，k指向右子结点
                    k++;
                }
                if (arr[k] > temp)
                {//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                    arr[i] = arr[k];
                    i = k;
                }
                else
                {
                    break;
                }
            }
            arr[i] = temp;//将temp值放到最终的位置
        }
    }