美文网首页
【数据结构】【C#】020-交换类排序:🌔快速排序(不稳定)(重

【数据结构】【C#】020-交换类排序:🌔快速排序(不稳定)(重

作者: lijianfex | 来源:发表于2018-10-18 18:16 被阅读4次

【算法改进要点 】 在上节讨论的冒泡排序中,由于扫描过程中只对相邻的两个元素进行比较,
因此在互换两个相邻元素时只能消除一个逆序。如果能通过两个(不相邻的)元素的交换,
消除待排序记录中的多个逆序,则会大大加快排序的速度。快速排序方法中的一次交换可能
消除多个逆序。

【 算法思想 】 从待排序记录序列中选取一个记录(通常选取第一个记录)为枢轴,其关键字
设为 K 1 ,然后将其余关键字小于 K 1 的记录移到前面,而将关键字大于 K 1 的记录移到后面,
结果将待排序记录序列分成两个子表,最后将关键字为 K 1 的记录插到其分界线的位置处。
将这个过程称作 一趟快速排序。通过一次划分后,就以关键字为 K 1 的记录为界,将待排序
序列分成了两个子表,且前面子表中所有记录的关键字均不大于 K 1 ,而后面子表中的所有
记录的关键字均不小于 K 1 。对分割后的子表继续按上述原则进行分割,直到所有子表的表
长不超过 1 为止,此时待排序记录序列就变成了一个有序表。

【算法步骤】
假设待划分序列为 r[left], r[left+1], … ,r[right],具体实现上述划分过程时,可以设两个指针 i 和 j,它们的初值分别为 left 和 right。首先将基准记录 r[left]移至变量 x 中,使r[left],即 r[i]相当于空单元,然后反复进行如下两个扫描过程,直到 i 和 j 相遇:
⑴ j 从右向左扫描,直到 r[j].key < x.key 时,将 r[j]移至空单元 r[i],此时 r[j]相当于空单元。
⑵ i 从左向右扫描,直到 r[i].key > x.key 时,将 r[i]移至空单元 r[j],此时 r[i]相当于空单元。
当 i 和 j 相遇时, r[i](或 r[j])相当于空单元,且 r[i]左边所有记录的关键字均不大于基准记录的关键字,而 r[i]右边所有记录的关键字均不小于基准记录的关键字。最后将基准记录移至 r[i]中,就完成了一次划分过程。对于 r[i]左边的子表和 r[i]右边的子表可采用同样的方法进行进一步划分。


C#实现:

快速排序:递归调用(挖坑法)
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

/// <summary>
/// 交类排序
/// </summary>
public class ChangeSort
{
/// <summary>
    /// 快排:(递归)挖坑法
    /// </summary>
    /// <param name="a"></param>
    /// <param name="startIndex"></param>
    /// <param name="endIndex"></param>
    public static void QuickSort_1(int[] a, int startIndex, int endIndex)
    {
        if (startIndex >= endIndex)
        {
            return;
        }

        int pivotIndex = GetPivotIndex(a, startIndex, endIndex);
        QuickSort_1(a, startIndex, pivotIndex - 1);
        QuickSort_1(a, pivotIndex + 1, endIndex);
    }

    /// <summary>
    /// 获得基准的位置:(填坑法)方法1
    /// </summary>
    /// <param name="a"></param>
    /// <param name="startIndex"></param>
    /// <param name="endIndex"></param>
    /// <returns></returns>
    public static int GetPivotIndex(int[] a, int startIndex, int endIndex)
    {
        int pivot = a[startIndex]; //取第一个元素为基准数
        int left = startIndex;
        int right = endIndex;


        int index = startIndex;//挖坑法:坑的位置

        while (left <= right)
        {
            //right 指针从右向左进行比较
            while (left <= right)
            {
                if (a[right] < pivot)
                {
                    a[left] = a[right];
                    index = right;
                    left++;
                    break;
                }
                right--;
            }

            //left 指针从左向右进行比较
            while (left <= right)
            {
                if (a[left] > pivot)
                {
                    a[right] = a[left];
                    index = left;
                    right--;
                    break;
                }
                left++;
            }
        }

        a[index] = pivot;
        return index;

    }
}

快速排序:非递归(使用栈消除递归)
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

/// <summary>
/// 交类排序
/// </summary>
public class ChangeSort
{
    /// <summary>
    /// 快速排序:(非递归)用栈消除递归
    /// </summary>
    /// <param name="a"></param>
    /// <param name="startIndex"></param>
    /// <param name="endIndex"></param>
    public static void QuickSort_2(int[] a, int startIndex, int endIndex)
    {
        if (startIndex >= endIndex)
        {
            return;
        }

        Stack<Dictionary<string, int>> quickSortStack = new Stack<Dictionary<string, int>>();

        Dictionary<string, int> rootParam = new Dictionary<string, int>();
        rootParam.Add("startIndex", startIndex);
        rootParam.Add("endIndex", endIndex);
        quickSortStack.Push(rootParam);

        while(quickSortStack.Count!=0)
        {
            Dictionary<string, int> param = quickSortStack.Pop();

            int pivotIndex = GetPivotIndex_2(a, param["startIndex"], param["endIndex"]);
            

            if(param["startIndex"]<pivotIndex-1)
            {
                Dictionary<string, int> leftParam = new Dictionary<string, int>();
                leftParam.Add("startIndex", param["startIndex"]);
                leftParam.Add("endIndex", pivotIndex - 1);
                quickSortStack.Push(leftParam);
               
            }
            if (pivotIndex+1 < param["endIndex"])
            {
                Dictionary<string, int> rightParam = new Dictionary<string, int>();
                rightParam.Add("startIndex", pivotIndex + 1);
                rightParam.Add("endIndex", param["endIndex"]);
                quickSortStack.Push(rightParam);               
            }
        }

    }

    /// <summary>
    /// 获得基准的位置:(指针法)方法2
    /// </summary>
    /// <param name="a"></param>
    /// <param name="startIndex"></param>
    /// <param name="endIndex"></param>
    /// <returns></returns>
    public static int GetPivotIndex_2(int[] a, int startIndex, int endIndex)
    {
        int pivot = a[startIndex]; //取第一个元素为基准数
        int left = startIndex;
        int right = endIndex;


        while (left < right)
        {
            while (left < right && a[right] >= pivot)
            {
                right--;
            }
            if (left < right)
            {
                a[left] = a[right];
                left++;
            }

            while (left < right && a[left] < pivot)
            {
                left++;
            }
            if (left < right)
            {
                a[right] = a[left];
                right--;
            }
        }

        a[left] = pivot;
        return left;
    }
}

测试用例;

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class _014_ChangeSort : MonoBehaviour
{


    void Start()
    {
        int[] a = Utilit.RandArray(20, 10);//new int[] { 4,3,2,1,0,5,6,7,8,9};

        int[] b = (int[])a.Clone();

       
        Debug.Log("---------------快速排序:挖坑法--------------");
        ChangeSort.QuickSort_1(a, 0, a.Length - 1);
        Utilit.Print(a, 0);


        Debug.Log("---------------快速排序:非递归--------------");
        ChangeSort.QuickSort_2(b, 0, a.Length - 1);
        Utilit.Print(b, 0);
    }


}

测试结果:

img.jpg

交换类排序总结:

img.jpg image.png

相关文章

网友评论

      本文标题:【数据结构】【C#】020-交换类排序:🌔快速排序(不稳定)(重

      本文链接:https://www.haomeiwen.com/subject/osfszftx.html