C#快速排序

1:需求

已知数组int[] max={72, 54, 59, 30, 31, 78, 2, 77, 82, 72};用快速排序算法按降序对其进行排列,并返回数组。

思路:

快速排序有两个方向,左边的i下标一直往右走,当a[i] <= a[center_index],其中center_index是中枢元素的数组下标,一般取为数组第0个元素。而右边的j下标一直往左走,当a[j] > a[center_index]。如果i和j都走不动了,i <= j, 交换a[i]和a[j],重复上面的过程,直到i>j。 交换a[j]和a[center_index],完成一趟快速排序。在中枢元素和a[j]交换的时候,很有可能把前面的元素的稳定性打乱,比如序列为 5 3 3 4 3 8 9 10 11, 现在中枢元素5和3(第5个元素,下标从1开始计)交换就会把元素3的稳定性打乱,所以快速排序是一个不稳定的排序算法,不稳定发生在中枢元素和a[j]交换的时刻。

2:代码

        static void Main()
        {
            array = new int[] { 72, 54, 59, 30, 31, 78, 2, 77, 82, 72 };
            QuickSort(0, array.Length - 1);
            Console.WriteLine("The Result: ");
            for (int i = 0; i < array.Length; i++)
            {
                Console.Write(array[i] + ", ");
            }
            Console.ReadKey();
        }

        private static int[] array;
        private static void QuickSort(int lowest, int highest)
        {
            if (array == null || lowest < 0 || lowest >= highest
            || highest >= array.Length)
            {
                return;
            }
            int low = lowest;
            int high = highest;
            int key = low++;
            for (; low <= high; )
            {
                if (key < high)
                {
                    if (array[key] > array[high])
                    {
                        array[high] = array[key] + (array[key] = array[high]) * 0;
                        key = high;
                    }
                    high--;
                }

                if (key > low)
                {
                    if (array[key] < array[low])
                    {
                        array[low] = array[key] + (array[key] = array[low]) * 0;
                        key = low;
                    }
                    low++;
                }
            }
            for (int i = 0; i < array.Length; i++)
            {
                Console.Write(array[i] + ", ");
            }
            Console.WriteLine();
            QuickSort(lowest, key - 1);
            QuickSort(key + 1, highest);
        }

3:时间复杂度

log2(n)*n

C#快速排序本文基于Creative Commons Attribution 2.5 China Mainland License发布,欢迎转载,演绎或用于商业目的,但是必须保留本文的署名http://www.cnblogs.com/luminji(包含链接)。如您有任何疑问或者授权方面的协商,请给我留言。
上一篇:Mybatis基于接口注解配置SQL映射器(二)


下一篇:小程序(uniapp)骨架屏应用