排序算法总结

交换类排序

冒泡排序精髓：
设置一个两层循环。外层遍历次数为比较次数，内层从前往后遍历所有元素，当前者大于后者则交换位置。

public void BubbleSort(int[] a)
        {
           int temp, upper = a.Length-1;
           for (int outer =1; outer<=upper; outer++)
            {
                //每完成一次外层遍历，最大的肯定在最后,所以少遍历outer个元素
                for (int inner = 0; inner <= upper-outer; inner++)
                {
                    if (arr[inner] > arr[inner + 1])
                    {
                        temp = arr[inner];
                        arr[inner] = arr[inner + 1];
                        arr[inner + 1] = temp;
                    }
                }
            }
        }

#快速排序精髓（分治）
将数组递归划分成两个子序列:设置pivot值，小于pivot的在pivot左边，大的在pivot右边。最先暂存的pivot值是为了给交换数值腾出位置，比较完后就附给中间值，因为比较都是以pivot来分大小，排左右的。

        public void QuickSort(int[] a,int low, int upper)
        {
           if (low< upper)
            {
                int pivotIndex = Partition(a, low, upper);
                //利用分之思想，将问题分成小块
                QuickSort(a, low, pivotIndex- 1);
                QuickSort(a, pivotIndex+ 1, upper);
            }
        }

        //划分子序列
        private int Partition(int[] a, int low, int upper)
        {
            int pivot = a[low];  //low作为比较的起点，暂存一下中轴值
            while (low< upper)//从两端交替向内扫描
            {
                 //low指针不动，upper指针扫描low右边
                while (low< upper&& a[upper] >= pivot) 
                    upper--;
                a[low] = a[upper];//将比pivot小的元素移向低端

                 //upper指针不动，low指针扫描upper左边
                while (upper>low&& a[low] <= pivot)
                    low++;
                a[upper] = a[low];//将比pivot大的元素移到高端
            }
            //low==high
            a[low] = pivot;  //将中轴元素附给中间这个位置
            return low;       //返回轴元素
        }

处理大数据量且无序的排序问题，快速排序是最快的。.Net 框架库类中的 Sort 方法就是用快速排序算法实现的。另外，快排中的第一个pivot最好由arr[(int)arr.GetUpperBound(0) / 2]来确定（除非数组随机无序）

选择类排序

简单选择排序精髓
设置两层循环。外层遍历所有元素，内层遍历外层之后元素，找到其中最小元素记录，然后和当前外层元素交换。

public void SelectionSort(int[] a)
        {
            //O(N^2+N)
            int minIndex, temp, upper = a.Length-1;
            //遍历次数
            for (int outer = 0; outer <= upper; outer++)
            {
                minIndex = outer;
                //找到最小值索引
                for (int inner = outer + 1; inner <= upper; inner++)
                {
                    if (arr[inner] < arr[minIndex])
                        minIndex = inner;
                }
                //交换
                temp = arr[outer];
                arr[outer] = arr[minIndex];
                arr[minIndex] = temp;
              //  DisplayElements();
            }
        }

插入类排序

直接插入排序精髓
把数组分为排好序的和没排好序的两半。设置两层循环，外层遍历第二个元素开始的所有元素，内层遍历排好序的元素。外层遍历元素在排序好的数中找位置：从后往前查找大于本身数直到有数小于本身，插入该位置。

 public void InsertSort(int[] a)
        {
            //O(N^2)
            int temp, inner;
            //遍历次数，从第二个数开始检查,第一个数默认有序
            for (int outer = 1; outer <= upper; outer++)
            {
                temp = arr[outer];
                inner = outer;
                while (inner > 0 && arr[inner - 1] >= temp)  //数据后移
                {
                    arr[inner] = arr[inner - 1];
                    inner -= 1;
                }
                arr[inner] = temp;
                //DisplayElements();
            }
        }

折半插入排序精髓
在直接插入排序的基础上，有效的减少比较次数，但是移动次数并不会改变。设置两重循环，外层循环遍历第二个元素开始的所有数据，内层设置两个同级循环，一个用来折半遍历；另一个用来移动数据。

public void BinInsertSort()
        {
            //所有待排序元素
            for (int i =  1; i <= upper; i++) 
            {
                int temp = arr[i];
                //前面有序子序列的范围
                int hi = i - 1;int lo = 0;

                while (lo <= hi)   //折半定位
                {
                    int half = (lo + hi) / 2;
                    if (arr[half] < temp)
                        lo = half + 1;
                    else
                        hi = half - 1;
                }
                for (int j = i - 1; j > hi; j--)//移动
                    arr[j + 1] = arr[j];
                arr[hi + 1] = temp;             //插入
            }
           // DisplayElements();
        }

希尔排序（直接插入排序改进版）
将待排序的元素分为多个子序列，使得每个子序列的元素个数相对较少，对各个子序列分别进行直接插入排序，待整个待排序序列“基本有序”后，再对所有元素进行一次直接插入排序。本算法的关键内容是对远距离而非相邻的数据项进行比较。当算法循环遍历数据集合的时候，每个数据项间的距离会缩短，直到算法对相邻数据项进行比较时才终止。

public void ShellSort()
        {
            int inner, temp;
            int h = 3;    //步长
            while (h > 0)
            {
                for (int outer = h; outer <= upper; outer++)
                {
                    temp = arr[outer];
                    inner = outer;
                    while ((inner > h - 1) && arr[inner - h] >= temp)
                    {
                        arr[inner] = arr[inner - h];
                        inner -= h;
                    }
                    arr[inner] = temp;
                }
                h = (h - 1) % 3;    //缩短步长再次排序
            }
            //DisplayElements();
        }

直接插入排序适合数据量少的情况下，后两个适合数据量大的的情况。同时，折半查找只是减少了比较次数、复杂度并没有降低。而希尔排序的复杂度受步长影响

分治类排序（递归）

1.快速排序（转上）
2.归并排序
这个算法把数据集合不断的分成两个部分，然后对每部分递归地进行
排序。当两个部分都排序好时，再用合并程序把它们组合在一起。
但是归并排序需要注意一个问题就是：划分出来的两个部分不一样长。这就要做一个规定：当主循环结束后，当且仅当两个数组中的一个数组还有元素时，可以使用两个额外的循环。

    /// <summary>
        /// 归并排序,分治法
        /// </summary>
        public void MergeSort()
        {
            //创建一个暂存数组,避免合并时反复申请内存
            int[] t = new int[arr.Length];
            Sort(arr,t, 0, arr.Length - 1);
            DisplayElements();
        }

        //递归排序
        public static void Sort(int[] a, int[] t, int low, int high)
        {
            if (low < high)
            {
                //划分待排序列
                int mid = (low + high) / 2;  
                Sort(a,t, low, mid);
                Sort(a,t, mid + 1, high);

                //合并
                Merge(a,t, low, mid, high);
            }
        }
        private static void Merge(int[] a, int[] t,int low, int mid, int high)
        {
            //m左序列起始指针，n右序列起始指针，k暂存数组起始指针
            int m = low, n = mid + 1, k = low;

            //比较左右两个序列上指针指的数字大小，小的先入数组
            while (n <= high && m <= mid)
            {
                if (a[m] > a[n])
                    t[k++] = a[n++];
                else
                    t[k++] = a[m++];
            }

            //如果两个子序列中有一个子序列先合并完了，把剩下的子序列全部加入暂存数组中
            //左序列还有剩下的
            while (n < high + 1)
                t[k++] = a[n++];
            //右序列还有剩下的
            while (m < mid + 1)
                t[k++] = a[m++];

            //把暂存数组里的数据再导回原来数组中
           for (int i = low; i <= high; i++)
                a[i] = t[i];
        }

为了形象化理解，参看图示：

图示

对比