温（Xue）习排序算法

最近忙着找工作，虽然排序算法用得到的情况不多，但不熟悉的话心里始终还是感觉没底。

于是今天给温习了其中的四个排序算法（与其说是温习，不如说是学习、、、因为感觉自己好像从来木有掌握过它们、、、）

一、选择排序

简单粗暴：将无序区变为有序区，每次将无序区中最小的挑选到最前面形成有序区。

例子：

5 3 7 8 4 原始数组

3 5 7 8 4 将3与5交换，因为后面的数字都比3大，所以不会再产生交换

3 4 7 8 5 同上，将 4与5交换

3 4 5 8 7 将5与7交换

3 4 5 7 8 将7与8交换

3 4 5 7 8

代码：

        /// <summary>

        /// 选择排序

        /// </summary>

        /// <param name="nList"></param>

        public static void SelectSort(int[] nList)

        {

            for (int i = ; i < nList.Length; i++)

            {

                for (int j = i; j < nList.Length; j++)

                {

                    if (nList[j] < nList[i])

                    {

                        int nTemp = nList[i];

                        nList[i] = nList[j];

                        nList[j] = nTemp;

                    }

                }

            }

        }

二、冒泡排序

生动形象：每一轮都将无序区中最大的数字弄到最后面，像冒泡一样

5 3 7 8 4 原始数组

3 5 7 8 4 比较5与3，发现5比3大，交换之

3 5 7 8 4 比较5与7，不变

3 5 7 8 4 比较7与8，不变

3 5 7 4 8 将4与8交换

3 5 7 4 剩下的无序区，重复以上步骤即可

代码：

        /// <summary>

        /// 冒泡排序

        /// </summary>

        /// <param name="nList"></param>

        public static void BubbleSort(int[] nList)

        {

            for (int i = nList.Length - ; i > ; i--)

            {

                for (int j = ; j < i; j++)

                {

                    if (nList[j] > nList[j + ])

                    {

                        int nTemp = nList[j];

                        nList[j] = nList[j + ];

                        nList[j + ] = nTemp;

                    }

                }

            }

        }

三、插入排序

望文生义：将元素插入到已经排序好的区域

3 5 7 8 4 原始数组

3 5 7 8 4 从5开始插入，直接放在末尾

3 5 7 8 4 将7放到末尾

3 5 7 8 4 将8放到末尾

3 4 5 7 8 将8、7、5后移，将4插入

代码：

        /// <summary>

        /// 插入排序

        /// </summary>

        /// <param name="nList"></param>

        public static void InserSort(int[] nList)

        {

            int nTemp;

            for (int i = ; i < nList.Length; i++)

            {

                nTemp = nList[i];//记住待插入元素

                for (int j = i - ; j >= ; j--)

                {

                    //若待插元素比当前元素小，则将当前元素往后移

                    if (nList[j] > nTemp)

                    {

                        nList[j + ] = nList[j];

                        if (j == )

                        {

                            nList[] = nTemp;

                        }

                    }

                    //反之，待插元素大于等于当前元素，则将待插元素放到当前元素的后面即可，并终止本轮循环

                    else

                    {

                        nList[j + ] = nTemp;

                        break;

                    }

                }

            }

        }

四、快速排序

快成一道闪电：改良的冒泡排序（但相对前面三种方法，掌握起来就要慢一些了。。。）

3 5 7 8 4 哨兵：3 nLeft ：5 nRight：4

、、、发现用这个来作为例子显然不合适嘛、、、来个加长版的，OK？

72 6 57 88 60 42 83 73 48 85 哨兵：72

x i j

取出72（此时nList为空），从j开始向左找到第一个比72小的数字：48，将其放到nList[0]中。

48 6 57 88 60 42 83 73 空 85

再从i开始向右找到第一个比72大的数，放到“空”的位置（注意，当i == j时此轮排序结束，所以要加判定）

48 6 57 空 60 42 83 73 88 85

重复以上步骤

48 6 57 42 60 空 83 73 88 85 此时 J 和 I会在“空”处相等，将前面的72填入“空”

48 6 57 42 60 72 83 73 88 85

后面用分治法继续快速排序[48,6,57,42,60]与[83,73,88,85]即可

代码：

        /// <summary>

        /// 快速排序

        /// </summary>

        public static void QuickSort(int[] nList,int nLow,int nHigh)

        {

            //终止条件

            if (nLow >= nHigh)

            {

                return;

            }

            //当nLeft 等于 nRight之时，结束此轮快速排序

            int nLeft = nLow;

            int nRight = nHigh;

            int nTemp = nList[nLow];

            while(nLeft < nRight)

            {

                while(nLeft < nRight && nList[nRight] >= nTemp)

                {

                    nRight--;

                }

                if (nLeft < nRight)

                {

                    nList[nLeft++] = nList[nRight];

                }

                while (nLeft < nRight && nList[nLeft] <= nTemp)

                {

                    nLeft++;

                }

                if (nLeft < nRight)

                {

                    nList[nRight--] = nList[nLeft];

                }

            }

            nList[nLeft] = nTemp;

            QuickSort(nList, nLow, nLeft - );

            QuickSort(nList, nLeft + , nHigh);

        }

巴特西

温（Xue）习排序算法

最新文章

热门文章