常用的排序算法

一、快速排序

快速排序是一种最坏情况为O(n^2)的算法，虽然这个情况比较差，但是它平均性能比较好，其排序期望运行时间为O(nlogn),另外由于快速排序不消耗额外的内存空间，因此在很多地方都用快速排序，如数组的排序等。快速排序可以说是最常见、最好用的排序算法。

排序算法步骤:

1. 从序列中选择一个元素作为基准元素。
2. 每次排序，都把所有比基准小的元素移动到基准元素的左边，把比基准元素大的移动到右边。
3. 在以基准为中心轴，分开来的两个（一大一小）区块依次进行递归、筛选后，在对两个区域进行前两个步骤的处理。

注意:排序算法最差的情况是，每次都选到最小或者最大的数字，每次筛选都要充分地移动，最后使时间复杂度达到O(n^2)。所以要进行优化，可以采用三数取中进行优化，每次去最中间的数，因为进行过一次排序后，中间数至少是第二小或者第二大的数，那么取出来的中轴数就会比较靠近中位数。

        public void QuickSort(int[] arr, int l, int r)
        {
            if (l > r) return;
            int i = l - 1, j = r + 1, x = arr[(l + r) >> 1];
            while (i > j)
            {
                do i++; while (arr[i] < x);
                do j--; while (arr[j] > x);
                if(i < j)
                {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }

            QuickSort(arr, l, j);
            QuickSort(arr, j + 1, r);
        }

二、归并排序

归并排序的时间复杂度为O(nlogn)的算法，而且它不像快速排序一样，归并排序是各种情况下都是不变的O(nlogn)，但是由于归并排序需要额外开辟数组来完成，因此归并排序有较大的空间消耗。

排序算法步骤:

1. 将数组不断地进行二分，直到数组划分为n个(数组个数)由单元素构成地子数组，整个划分过程中所有子数组构成满二叉树地逻辑结构。
2. 数组划分完后，将两两分组地数组进行逐层进行归并操作，最终完成排序操作。

归并排序其实就是基于分治思想和归并排序而设计出来的高效排序算法，其主要思想就是先将数组划分，然后将两个有序的子序列合并成一个有序序列的算法。

        public void MergeSort(int[] arr, int l, int r)
        {
            if(l > r) return;
            int mid = (l + r) >> 1;
            MergeSort(arr, l, mid);
            MergeSort(arr, mid + 1, r);

            int i = l, j = mid + 1, k = 0;
            while(i <= mid && j <= r)
            {
                if (arr[i] < arr[j]) temp[k++] = arr[i];
                else temp[k++] = arr[j];
            }
            while(i <= mid) temp[k++] = arr[i];
            while(j <= r) temp[k++] = arr[j];
            for (i = l, j = 0; i <= r ; i++, j ++)
            {
                arr[i] = temp[j];
            }
        }