首页 > 代码库 > 快速排序

快速排序

2024-09-06 02:55:41   211人阅读

快速排序是不稳定的排序，但其中逻辑比较怪。

网上的教程一般只介绍第一轮排序，省略第二轮

以至于学习时把分割子序列的步骤给漏了，浪费了不少时间

这里推荐这个教程，非常详细：http://www.cnblogs.com/jingmoxukong/p/4302891.html

 

首先取一个关键数，并不断来回和左右两边的数做比较

然后交换位置，直到左右两边都没有可以交换的数时，一轮结束

将左右两边分别拆成子序列，分别再进行快速排序

直到左右两边的数字不能再拆为止。

 

以一串数为例：5,1,3,2,1。5作为关键字

1.比较左侧，没有可交换，5,1,3,2,1

2.比较右侧，5和1交换，1,5,3,2,1

3.比较左侧，没有可交换，1,5,3,2,1

4.比较右侧，5和1交换，1,1,3,2,5

5.发现没有交换，对5左右两侧进行拆分，{1,1,3,2}和{}。对右侧序列以1为关键字继续排序

6.1,1,3,2，左右没有可交换，将1,3,2拆出继续排序

7.1,3,2，左右没有可交换，将3,2拆出继续排序

8.3,2，比较左侧没有可交换，比较右侧2与3交换

9.所有子序列无法拆分，排序结束。结果：1,1,2,3,5

 

脚本(以中间作为关键数)：

[ContextMenu("Test")]
void Test()
{
    var array = new int[] { 13, 34, 1, 5, 21, 3, 2, 8, 1 };
    Quick_Sort(array);

    Debug.Log("Final: " + string.Join(",", array.Select(m => m.ToString()).ToArray()));
}

void Quick_Sort(int[] array)
{
    Quick_Sort(array, 0, array.Length - 1);
}

void Quick_Sort(int[] array, int leftIndex, int rightIndex)
{
    if (rightIndex - leftIndex < 2) return;

    var key = leftIndex + ((rightIndex - leftIndex) / 2);
    var direction = -1;
    var flag = 0;

    while (true)
    {
        if (direction == -1)
        {
            for (int i = leftIndex; i <= key; i++)
            {
                if (array[i] > array[key])
                {
                    Swap(array, i, key);
                    key = i;
                    flag = -1;
                    break;
                }
            }
        }
        else
        {
            for (int i = key + 1; i <= rightIndex; i++)
            {
                if (array[key] > array[i])
                {
                    Swap(array, i, key);
                    key = i;
                    flag = -1;
                    break;
                }
            }
        }

        direction *= -1;
        flag++;

        //左右两边都没有的情况
        if (flag == 2)
        {
            //再拆分成两个子序列进行排序
            Quick_Sort(array, 0, key);
            Quick_Sort(array, key + 1, rightIndex);
            break;
        }
    }
}

void Swap(int[] array, int x, int y)
{
    var tmp = array[x];
    array[x] = array[y];
    array[y] = tmp;
}

打印:1,1,2,3,5,8,13,21,34

快速排序


联系
我们