365体育官网排序算法是大家编制程序中碰到的最多的算法,排序算法是我们编程中遇见的最多的算法

365体育官网 1

八种重大排序算法的C#实现 (一),

简介

排序算法是大家编制程序中相遇的最多的算法。近来主流的算法有8种。

  平均时间复杂度从高到低依次是:

    
冒泡排序(o(n2)),采取排序(o(n2)),插入排序(o(n2)),堆排序(o(nlogn)),

     归并排序(o(nlogn)),火速排序(o(nlogn)),
希尔排序(o(n1.25)),基数排序(o(n))

那几个平均时间复杂度是参照维基百科排序算法罗列的。

是计量的理论平均值,并不表示你的代码落成能落得那样的等级次序。

比方希尔排序,时间复杂度是由精选的上升的幅度决定的。基数排序时间复杂度最小,

但笔者实现的基数排序的速度并不是最快的,后边的结果测试图能够观察。

本文代码落成应用的数码源类型为IList<int>,那样能够兼容int[]和List<int>(虽然int[]有ToList(),

List<int>有ToArray(),哈哈!)。

365体育官网 2

挑选排序

选取排序是本身认为最简便易行暴力的排序情势了。

先前刚接触排序算法的时候,认为算法太多搞不清,唯独记得选拔排序的做法及贯彻。

规律:寻觅出席排序的数组最大值,放到最终(或找到最小值放到起来) 维基入口

落成如下:

public static void SelectSort(IList<int> data)
        {
            for (int i = 0; i < data.Count - 1; i++)
            {
                int min = i;
                int temp = data[i];
                for (int j = i + 1; j < data.Count; j++)
                {
                    if (data[j] < temp)
                    {
                        min = j;
                        temp = data[j];
                    }
                }
                if (min != i)
                    Swap(data, min, i);
            }
        }

进度解析:将剩余数组的纤维数沟通到起来。

简介

排序算法是大家编制程序中遇到的最多的算法。近期主流的算法有八种。

  平均时间复杂度从高到低依次是:

    
冒泡排序(o(n2)),选拔排序(o(n2)),插入排序(o(n2)),堆排序(o(nlogn)),

     归并排序(o(nlogn)),快捷排序(o(nlogn)),
希尔排序(o(n1.25)),基数排序(o(n))

那个平均时间复杂度是参照维基百科排序算法罗列的。

是计算的申辩平均值,并不意味你的代码完成能达成如此的程度。

譬如希尔排序,时间复杂度是由精选的宽窄决定的。基数排序时间复杂度最小,

但小编达成的基数排序的速度并不是最快的,后边的结果测试图能够看看。

本文代码完毕利用的数目源类型为IList<int>,那样能够包容int[]和List<int>(虽然int[]有ToList(),

List<int>有ToArray(),哈哈!)。

冒泡排序

冒泡排序是笔试面试日常考的剧情,固然它是那些算法里排序速度最慢的(汗),前边有测试为证。

规律:从头开端,每叁个因素和它的下一个因素相比,借使它大,就将它与比较的要素沟通,不然不动。

那意味着,大的成分总是在向后慢慢挪动直到遭受比它更加大的因素。所以每1轮交流完明尼阿波利斯能将最大值

冒到最终。  维基入口

贯彻如下:

public static void BubbleSort(IList<int> data)
        {
            for (int i = data.Count - 1; i > 0; i--)
            {
                for (int j = 0; j < i; j++)
                {
                    if (data[j] > data[j + 1])
                        Swap(data, j, j + 1);
                }
            }
        }

进度解析:中需求专注的是j<i,每轮冒完泡必然会将最大值排到数组末尾,所以供给排序的数相应是在削减的。

多多网络版本每轮冒完泡后依旧依旧将具有的数进行第1轮冒泡即j<data.Count-一,那样会大增比较次数。

选料排序

采取排序是小编觉着最简易暴力的排序格局了。

先前刚接触排序算法的时候,认为算法太多搞不清,唯独记得采取排序的做法及落成。

原理:搜索参与排序的数组最大值,放到最后(或找到最小值放到伊始) 维基入口

福寿年高如下:

public static void SelectSort(IList<int> data)
        {
            for (int i = 0; i < data.Count - 1; i++)
            {
                int min = i;
                int temp = data[i];
                for (int j = i + 1; j < data.Count; j++)
                {
                    if (data[j] < temp)
                    {
                        min = j;
                        temp = data[j];
                    }
                }
                if (min != i)
                    Swap(data, min, i);
            }
        }

经过解析:将剩余数组的细小数交流到起来。

由此标记进步冒泡排序

在维基上收看,能够透过充裕标记来识别剩余的数是还是不是早已平稳来收缩相比较次数。认为很风趣,能够试试。

兑现如下:

public static void BubbleSortImprovedWithFlag(IList<int> data)
        {
            bool flag;
            for (int i = data.Count - 1; i > 0; i--)
            {
                flag = true;
                for (int j = 0; j < i; j++)
                {
                    if (data[j] > data[j + 1])
                    {
                        Swap(data, j, j + 1);
                        flag = false;
                    }
                }
                if (flag) break;
            }
        }

进度解析:发现某轮冒泡未有任何数进行沟通(即现已稳步),就跳出排序。

自家开场也感觉这么些方式是应有有不易效用的,但是实际测试结果并不及想的那样。和未优化耗时同一(对于自由数列)。

由果推因,那么相应是冒泡排序对于随意数列,当剩余数列有序的时候,也没多少个数要排列了!?

唯独假如已经是雷打不动数列或许局地有序的话,这么些冒泡方法将会升级一点都不小速度。

冒泡排序

冒泡排序是笔试面试平常考的始末,固然它是这一个算法里排序速度最慢的(汗),前边有测试为证。

原理:从头开头,每三个要素和它的下一个成分相比,若是它大,就将它与相比较的因素交流,不然不动。

那表示,大的要素总是在向后稳步挪动直到遇到比它越来越大的成分。所以每一轮沟通完伊斯兰堡能将最大值

冒到终极。  维基入口

得以落成如下:

public static void BubbleSort(IList<int> data)
        {
            for (int i = data.Count - 1; i > 0; i--)
            {
                for (int j = 0; j < i; j++)
                {
                    if (data[j] > data[j + 1])
                        Swap(data, j, j + 1);
                }
            }
        }

进程解析:中供给注意的是j<i,每轮冒完泡必然会将最大值排到数组末尾,所以须要排序的数相应是在调整和减弱的。

过多网络版本每轮冒完泡后如故依旧将富有的数进行第三轮冒泡即j<data.Count-1,那样会增添相比次数。

鸡尾酒排序(来回排序)

通过标记提高冒泡排序

在维基上见到,可以因此抬高标记来识别剩余的数是还是不是已经稳步来压缩相比次数。认为很有意思,能够尝试。

达成如下:

public static void BubbleSortImprovedWithFlag(IList<int> data)
        {
            bool flag;
            for (int i = data.Count - 1; i > 0; i--)
            {
                flag = true;
                for (int j = 0; j < i; j++)
                {
                    if (data[j] > data[j + 1])
                    {
                        Swap(data, j, j + 1);
                        flag = false;
                    }
                }
                if (flag) break;
            }
        }

经过解析:开掘某轮冒泡未有其余数进行置换(即现已平稳),就跳出排序。

本人初阶也认为这么些格局是应有有不易效果的,不过实际上测试结果并不及想的那么。和未优化耗费时间1致(对于随便数列)。

由果推因,那么应该是冒泡排序对于自由数列,当剩余数列有序的时候,也没多少个数要排列了!?

不过假如已经是铁板钉钉数列或许有些有序的话,这一个冒泡方法将会进步异常的大速度。

对冒泡排序进行更加大的优化

冒泡排序只是单向冒泡,而干白来回反复双向冒泡。

规律:自左向右将时局冒到最终,然后将剩余数列再自右向左将小数冒到开端,如此循环。维基入口

完毕如下:

public static void BubbleCocktailSort(IList<int> data)
        {
            bool flag;
            int m = 0, n = 0;
            for (int i = data.Count - 1; i > 0; i--)
            {
                flag = true;
                if (i % 2 == 0)
                {
                    for (int j = n; j < data.Count - 1 - m; j++)
                    {
                        if (data[j] > data[j + 1])
                        {
                            Swap(data, j, j + 1);
                            flag = false;
                        }
                    }
                    if (flag) break;
                    m++;
                }
                else
                {
                    for (int k = data.Count - 1 - m; k > n; k--)
                    {
                        if (data[k] < data[k - 1])
                        {
                            Swap(data, k, k - 1);
                            flag = false;
                        }
                    }
                    if (flag) break;
                    n++;
                }
            }
        }

进度解析:分析第i轮冒泡,i是偶数则将剩余数列最大值向右冒泡至末尾,是奇数则将剩余数列最小值

向左冒泡至开头。对于剩余数列,n为始,data.Count-一-m为末。

来回冒泡比单向冒泡:对于自由数列,更便于获得稳步的剩余数列。由此这里运用标志将会晋级的愈益显然。

朗姆酒排序(来回排序)

插入排序

插入排序是一种对于有序数列高速的排序。格外聪明的排序。只是对于自由数列,效能一般,交流的作用高。

规律:通过创设有序数列,将未排序的数从后迈入相比较,找到适当岗位并插入。维基入口

先是个数当作有序数列。

兑现如下:

public static void InsertSort(IList<int> data)
        {
            int temp;
            for (int i = 1; i < data.Count; i++)
            {
                temp = data[i];
                for (int j = i - 1; j >= 0; j--)
                {
                    if (data[j] > temp)
                    {
                        data[j + 1] = data[j];
                        if (j == 0)
                        {
                            data[0] = temp;
                            break;
                        }
                    }
                    else
                    {
                        data[j + 1] = temp;
                        break;
                    }
                }
            }
        }

经过解析:就要排序的数(索引为i)存款和储蓄起来,向前查找合适岗位j+壹,将i-1到j+1的要素依次向后

移动壹位,空出j+一,然后将以前存款和储蓄的值放在那个岗位。

其一措施写的不及维基上的轻便清晰,由杨晓培好岗位是j+一所以多出了对j==0的剖断,但其实际效果用影响无差异。

建议依据维基和本人写的排序,自行采纳。

对冒泡排序实行更加大的优化

冒泡排序只是单向冒泡,而干白来回反复双向冒泡。

规律:自左向右将时局冒到结尾,然后将剩余数列再自右向左将小数冒到起来,如此循环。维基入口

贯彻如下:

public static void BubbleCocktailSort(IList<int> data)
        {
            bool flag;
            int m = 0, n = 0;
            for (int i = data.Count - 1; i > 0; i--)
            {
                flag = true;
                if (i % 2 == 0)
                {
                    for (int j = n; j < data.Count - 1 - m; j++)
                    {
                        if (data[j] > data[j + 1])
                        {
                            Swap(data, j, j + 1);
                            flag = false;
                        }
                    }
                    if (flag) break;
                    m++;
                }
                else
                {
                    for (int k = data.Count - 1 - m; k > n; k--)
                    {
                        if (data[k] < data[k - 1])
                        {
                            Swap(data, k, k - 1);
                            flag = false;
                        }
                    }
                    if (flag) break;
                    n++;
                }
            }
        }

经过解析:分析第i轮冒泡,i是偶数则将剩余数列最大值向右冒泡至末尾,是奇数则将剩余数列最小值

向左冒泡至开端。对于剩余数列,n为始,data.Count-一-m为末。

过往冒泡比单向冒泡:对于自由数列,更便于获取稳步的剩余数列。因而这里运用标志将会升级的一发显眼。

二分查找法优化插入排序

插入排序首要专门的学问是在一如既往的数列中对要排序的数查找合适的任务,而追寻里面卓绝的二分查找法正能够适用。

规律:通过二分查找法的章程找到3个地方索引。当要排序的数插入这几个岗位时,大于前1个数,小于后叁个数。

兑现如下:

public static void InsertSortImprovedWithBinarySearch(IList<int> data)
        {
            int temp;
            int tempIndex;
            for (int i = 1; i < data.Count; i++)
            {
                temp = data[i];
                tempIndex = BinarySearchForInsertSort(data, 0, i, i);
                for (int j = i - 1; j >= tempIndex; j--)
                {
                    data[j + 1] = data[j];
                }
                data[tempIndex] = temp;
            }
        }

        public static int BinarySearchForInsertSort(IList<int> data, int low, int high, int key)
        {
            if (low >= data.Count - 1)
                return data.Count - 1;
            if (high <= 0)
                return 0;
            int mid = (low + high) / 2;
            if (mid == key) return mid;
            if (data[key] > data[mid])
            {
                if (data[key] < data[mid + 1])
                    return mid + 1;
                return BinarySearchForInsertSort(data, mid + 1, high, key);
            }
            else  // data[key] <= data[mid]
            {
                if (mid - 1 < 0) return 0;
                if (data[key] > data[mid - 1])
                    return mid;
                return BinarySearchForInsertSort(data, low, mid - 1, key);
            }
        }

进度解析:要求注意的是二分查找方法完成中high-low==1的时候mid==low,所以要求33行

mid-壹<0即mid==0的推断,不然下行会索引越界。

插入排序

插入排序是1种对于有序数列高速的排序。卓殊聪明的排序。只是对于随便数列,效能一般,交换的功能高。

规律:通过创设有序数列,将未排序的数从后迈入相比,找到适当岗位并插入。维基入口

第一个数当作有序数列。

金镶玉裹福禄双全如下:

public static void InsertSort(IList<int> data)
        {
            int temp;
            for (int i = 1; i < data.Count; i++)
            {
                temp = data[i];
                for (int j = i - 1; j >= 0; j--)
                {
                    if (data[j] > temp)
                    {
                        data[j + 1] = data[j];
                        if (j == 0)
                        {
                            data[0] = temp;
                            break;
                        }
                    }
                    else
                    {
                        data[j + 1] = temp;
                        break;
                    }
                }
            }
        }

进度解析:将要排序的数(索引为i)存储起来,向前查找合适岗位j+一,将i-一到j+1的因素依次向后

移步一人,空出j+一,然后将事先存款和储蓄的值放在这些地方。

那些方法写的不及维基上的简练清晰,由于方便岗位是j+一所以多出了对j==0的剖断,但实际功效影响无差别。

提出依据维基和自家写的排序,自行选取。

敏捷排序

快快排序是1种有效相比较多的快捷排序。它富含了“分而治之”以及“哨兵”的思考。

规律:从数列中甄选贰个数作为“哨兵”,使比它小的放在它的左侧,比它大的位于它的动手。将在排序是数列递归地撩拨到

小小数列,每一遍都让分割出的数列符合“哨兵”的规则,自然就将数列变得有序。 维基入口

落到实处如下:

public static void QuickSortStrict(IList<int> data)
        {
            QuickSortStrict(data, 0, data.Count - 1);
        }

        public static void QuickSortStrict(IList<int> data, int low, int high)
        {
            if (low >= high) return;
            int temp = data[low];
            int i = low + 1, j = high;
            while (true)
            {
                while (data[j] > temp) j--;
                while (data[i] < temp && i < j) i++;
                if (i >= j) break;
                Swap(data, i, j);
                i++; j--;
            }
            if (j != low)
                Swap(data, low, j);
            QuickSortStrict(data, j + 1, high);
            QuickSortStrict(data, low, j - 1);
        }

进度解析:取的哨兵是数列的第2个值,然后从第二个和结尾同时研究,左侧要呈现的是稍差于哨兵的值,

故而要找到不低于的i,右边要浮现的是出乎哨兵的值,所以要找到不当先的j。将找到的i和j的数交流,

如此那般能够减掉沟通次数。i>=j时,数列全体招来了贰回,而不符合条件j必然是在小的那1边,而哨兵

是首先个数,地方本应是低于自身的数。所以将哨兵与j调换,使符合“哨兵”的条条框框。

本条版本的短处在于壹旦是有序数列排序的话,递归次数会很吓人的。

二分查找法优化插入排序

插入排序首要专门的学问是在平稳的数列中对要排序的数查找合适的任务,而搜索里面卓越的二分查找法正能够适用。

规律:通过二分查找法的格局找到3个地方索引。当要排序的数插入那几个岗位时,大于前贰个数,小于后二个数。

完毕如下:

public static void InsertSortImprovedWithBinarySearch(IList<int> data)
        {
            int temp;
            int tempIndex;
            for (int i = 1; i < data.Count; i++)
            {
                temp = data[i];
                tempIndex = BinarySearchForInsertSort(data, 0, i, i);
                for (int j = i - 1; j >= tempIndex; j--)
                {
                    data[j + 1] = data[j];
                }
                data[tempIndex] = temp;
            }
        }

        public static int BinarySearchForInsertSort(IList<int> data, int low, int high, int key)
        {
            if (low >= data.Count - 1)
                return data.Count - 1;
            if (high <= 0)
                return 0;
            int mid = (low + high) / 2;
            if (mid == key) return mid;
            if (data[key] > data[mid])
            {
                if (data[key] < data[mid + 1])
                    return mid + 1;
                return BinarySearchForInsertSort(data, mid + 1, high, key);
            }
            else  // data[key] <= data[mid]
            {
                if (mid - 1 < 0) return 0;
                if (data[key] > data[mid - 1])
                    return mid;
                return BinarySearchForInsertSort(data, low, mid - 1, key);
            }
        }

进度解析:须求专注的是二分查找方法实现中high-low==一的时候mid==low,所以供给3叁行

mid-一<0即mid==0的论断,不然下行会索引越界。

另三个版本

那是维基上的叁个C#本子,小编觉着很有意思。这一个本子并未严厉符合“哨兵”的平整。但却将“分而治之”

以及“哨兵”观念融入个中,代码简洁。

完结如下:

public static void QuickSortRelax(IList<int> data)
        {
            QuickSortRelax(data, 0, data.Count - 1);
        }

        public static void QuickSortRelax(IList<int> data, int low, int high)
        {
            if (low >= high) return;
            int temp = data[(low + high) / 2];
            int i = low - 1, j = high + 1;
            while (true)
            {
                while (data[++i] < temp) ;
                while (data[--j] > temp) ;
                if (i >= j) break;
                Swap(data, i, j);
            }
            QuickSortRelax(data, j + 1, high);
            QuickSortRelax(data, low, i - 1);
        }

经过解析:取的哨兵是数列中间的数。将数列分成两波,左边小于等于哨兵,左边超过等于哨兵。

也正是说,哨兵不肯定处于两波数的中等。就算哨兵不在中间,但不要紧碍“哨兵”的想想的落到实处。所以

以此完毕也得以直达快捷排序的功力。但却变成了每一回递归完结,要排序的数列数总和没有收缩(除非i==j)。

迅猛排序

十分的快排序是一种有效相比多的登时排序。它含有了“分而治之”以及“哨兵”的沉思。

规律:从数列中精选贰个数作为“哨兵”,使比它小的位于它的右侧,比它大的位于它的右手。就要排序是数列递归地划分到

微小数列,每便都让分割出的数列符合“哨兵”的规则,自然就将数列变得平稳。 维基入口

兑现如下:

public static void QuickSortStrict(IList<int> data)
        {
            QuickSortStrict(data, 0, data.Count - 1);
        }

        public static void QuickSortStrict(IList<int> data, int low, int high)
        {
            if (low >= high) return;
            int temp = data[low];
            int i = low + 1, j = high;
            while (true)
            {
                while (data[j] > temp) j--;
                while (data[i] < temp && i < j) i++;
                if (i >= j) break;
                Swap(data, i, j);
                i++; j--;
            }
            if (j != low)
                Swap(data, low, j);
            QuickSortStrict(data, j + 1, high);
            QuickSortStrict(data, low, j - 1);
        }

经过解析:取的哨兵是数列的首先个值,然后从第一个和尾声同时搜寻,左边要显得的是小于哨兵的值,

由此要找到不低于的i,左边要呈现的是过量哨兵的值,所以要找到不高于的j。将找到的i和j的数交流,

那般能够裁减沟通次数。i>=j时,数列全体追寻了1回,而不符合条件j必然是在小的那1端,而哨兵

是第3个数,地方本应是稍低于本身的数。所以将哨兵与j交流,使符合“哨兵”的平整。

以此版本的后天不足在于壹旦是平稳数列排序的话,递归次数会很吓人的。

本着那几个版本的欠缺,笔者实行了优化

贯彻如下:

public static void QuickSortRelaxImproved(IList<int> data)
        {
            QuickSortRelaxImproved(data, 0, data.Count - 1);
        }

        public static void QuickSortRelaxImproved(IList<int> data, int low, int high)
        {
            if (low >= high) return;
            int temp = data[(low + high) / 2];
            int i = low - 1, j = high + 1;
            int index = (low + high) / 2;
            while (true)
            {
                while (data[++i] < temp) ;
                while (data[--j] > temp) ;
                if (i >= j) break;
                Swap(data, i, j);
                if (i == index) index = j;
                else if (j == index) index = i;
            }
            if (j == i)
            {
                QuickSortRelaxImproved(data, j + 1, high);
                QuickSortRelaxImproved(data, low, i - 1);
            }
            else //i-j==1
            {
                if (index >= i)
                {
                    if (index != i)
                        Swap(data, index, i);
                    QuickSortRelaxImproved(data, i + 1, high);
                    QuickSortRelaxImproved(data, low, i - 1);
                }
                else //index < i
                {
                    if (index != j)
                        Swap(data, index, j);
                    QuickSortRelaxImproved(data, j + 1, high);
                    QuickSortRelaxImproved(data, low, j - 1);
                }
            }
        }

public static void QuickSortRelaxImproved(IList<int> data)
        {
            QuickSortRelaxImproved(data, 0, data.Count - 1);
        }

        public static void QuickSortRelaxImproved(IList<int> data, int low, int high)
        {
            if (low >= high) return;
            int temp = data[(low + high) / 2];
            int i = low - 1, j = high + 1;
            int index = (low + high) / 2;
            while (true)
            {
                while (data[++i] < temp) ;
                while (data[--j] > temp) ;
                if (i >= j) break;
                Swap(data, i, j);
                if (i == index) index = j;
                else if (j == index) index = i;
            }
            if (j == i)
            {
                QuickSortRelaxImproved(data, j + 1, high);
                QuickSortRelaxImproved(data, low, i - 1);
            }
            else //i-j==1
            {
                if (index >= i)
                {
                    if (index != i)
                        Swap(data, index, i);
                    QuickSortRelaxImproved(data, i + 1, high);
                    QuickSortRelaxImproved(data, low, i - 1);
                }
                else //index < i
                {
                    if (index != j)
                        Swap(data, index, j);
                    QuickSortRelaxImproved(data, j + 1, high);
                    QuickSortRelaxImproved(data, low, j - 1);
                }
            }
        }

进度解析:定义了3个变量Index,来追踪哨兵的职分。开掘哨兵最终在低于自身的那堆,

这就与j沟通,不然与i调换。达到每一回递归都能收缩要排序的数列数总和的目标。

365体育官网 3

上述动图由“图斗罗”提供

另一个版本

那是维基上的3个C#本子,小编感觉很有意思。那个版本并不曾严厉符合“哨兵”的条条框框。但却将“分而治之”

以及“哨兵”思想融入个中,代码简洁。

兑现如下:

public static void QuickSortRelax(IList<int> data)
        {
            QuickSortRelax(data, 0, data.Count - 1);
        }

        public static void QuickSortRelax(IList<int> data, int low, int high)
        {
            if (low >= high) return;
            int temp = data[(low + high) / 2];
            int i = low - 1, j = high + 1;
            while (true)
            {
                while (data[++i] < temp) ;
                while (data[--j] > temp) ;
                if (i >= j) break;
                Swap(data, i, j);
            }
            QuickSortRelax(data, j + 1, high);
            QuickSortRelax(data, low, i - 1);
        }

进度解析:取的哨兵是数列中间的数。将数列分成两波,左边小于等于哨兵,左边超越等于哨兵。

也正是说,哨兵不必然处于两波数的中等。即便哨兵不在中间,但不要紧碍“哨兵”的沉思的贯彻。所以

其壹落成也足以直达飞快排序的作用。但却促成了每一遍递归落成,要排序的数列数总和未有滑坡(除非i==j)。

本着那几个版本的通病,作者进行了优化

兑现如下:

public static void QuickSortRelaxImproved(IList<int> data)
        {
            QuickSortRelaxImproved(data, 0, data.Count - 1);
        }

        public static void QuickSortRelaxImproved(IList<int> data, int low, int high)
        {
            if (low >= high) return;
            int temp = data[(low + high) / 2];
            int i = low - 1, j = high + 1;
            int index = (low + high) / 2;
            while (true)
            {
                while (data[++i] < temp) ;
                while (data[--j] > temp) ;
                if (i >= j) break;
                Swap(data, i, j);
                if (i == index) index = j;
                else if (j == index) index = i;
            }
            if (j == i)
            {
                QuickSortRelaxImproved(data, j + 1, high);
                QuickSortRelaxImproved(data, low, i - 1);
            }
            else //i-j==1
            {
                if (index >= i)
                {
                    if (index != i)
                        Swap(data, index, i);
                    QuickSortRelaxImproved(data, i + 1, high);
                    QuickSortRelaxImproved(data, low, i - 1);
                }
                else //index < i
                {
                    if (index != j)
                        Swap(data, index, j);
                    QuickSortRelaxImproved(data, j + 1, high);
                    QuickSortRelaxImproved(data, low, j - 1);
                }
            }
        }

public static void QuickSortRelaxImproved(IList<int> data)
        {
            QuickSortRelaxImproved(data, 0, data.Count - 1);
        }

        public static void QuickSortRelaxImproved(IList<int> data, int low, int high)
        {
            if (low >= high) return;
            int temp = data[(low + high) / 2];
            int i = low - 1, j = high + 1;
            int index = (low + high) / 2;
            while (true)
            {
                while (data[++i] < temp) ;
                while (data[--j] > temp) ;
                if (i >= j) break;
                Swap(data, i, j);
                if (i == index) index = j;
                else if (j == index) index = i;
            }
            if (j == i)
            {
                QuickSortRelaxImproved(data, j + 1, high);
                QuickSortRelaxImproved(data, low, i - 1);
            }
            else //i-j==1
            {
                if (index >= i)
                {
                    if (index != i)
                        Swap(data, index, i);
                    QuickSortRelaxImproved(data, i + 1, high);
                    QuickSortRelaxImproved(data, low, i - 1);
                }
                else //index < i
                {
                    if (index != j)
                        Swap(data, index, j);
                    QuickSortRelaxImproved(data, j + 1, high);
                    QuickSortRelaxImproved(data, low, j - 1);
                }
            }
        }

经过解析:定义了3个变量Index,来追踪哨兵的职责。开掘哨兵最终在低于自个儿的那堆,

那就与j交换,不然与i调换。达到每一次递归都能减小要排序的数列数总和的目标。

365体育官网 4

如上动图由“图斗罗”提供

http://www.bkjia.com/C\_jc/1233542.htmlwww.bkjia.comtruehttp://www.bkjia.com/C\_jc/1233542.htmlTechArticle8种主要排序算法的C\#实现 (一), 简单介绍排序算法是大家编程中遭受的最多的算法。目前主流的算法有八种。
平均时间复杂度从高到低依次…

相关文章