C#-记录几个排序算法(选择/插入/冒泡/希尔)

标签：rawList temp index C# List int 冒泡 排序

 

给定一组数据，使用不同的算法对其进行递增排序：

int[] rawList = { 12, 33, 21, 2, 43, 5, 67, 8, 96, 4, 22, 36, 23, 42, 90 };

选择排序：找到最大的数值，交换在最后一位，再找剩下的最大数值，交换在倒数第二位，再找剩下最大的数值，交换在倒数第三位，依次类推.....

    public static List<int> SelectSort(int[] rawList)
    {
        int endIndex = rawList.Length - 1;
        for (int j = 0; j <= endIndex; j++)
        {
            int maxIndex = -1;
            int maxValue = int.MinValue;
            for (int i = 0; i <= endIndex - j; i++)
            {
                compareTimes++;
                if (rawList[i] > maxValue)
                {
                    maxValue = rawList[i];
                    maxIndex = i;
                }
            }//找到剩下的最大数值
            if (maxIndex != -1)
            {
                int temp = rawList[maxIndex];
                rawList[maxIndex] = rawList[endIndex - j];
                rawList[endIndex - j] = temp;
            }//将该数值交换在最后位
        }
        return rawList.ToList();
    }

View Code

插入排序：需要另建立一个List，将第一位先放入List，再放入第二位List并排序，再放入第三位并排序，第四位依次类推.......

    public static List<int> InsertSort(int[] rawList)
    {
        List<int> newList = new List<int>();
        for (int i = 0; i < rawList.Length; i++)
        {
            int index = newList.Count;
            for (int j = 0; j < newList.Count; j++)
            {
                if (rawList[i] < newList[j])
                {
                    index = j;
                    break;
                }
            }
            newList.Insert(index, rawList[i]);
        }
        return newList;
    }

View Code

冒泡排序：第1位和第2位比较，大的交换到后面，然后第2和第3比较，第3和第4比较.....，比一遍后最大值已交换至最后，然后剩余的数值重复上述操作，直至无剩余的数值。

    public static List<int> BubbleSort(int[] rawList)
    {
        for (int i = 0; i < rawList.Length - 1; i++)
        {
            for (int j = 0; j < rawList.Length - 1 - i; j++)
                Swap(rawList, j);//比较并交换第j和j+1位
        }
        return rawList.ToList();
    }
    static void Swap(int[] rawList, int index)
    {
        if (rawList[index] > rawList[index + 1])
        {
            int temp = rawList[index];
            rawList[index] = rawList[index + 1];
            rawList[index + 1] = temp;
        }
    }

View Code

冒泡的递归实现：

   public static List<int> BubbleSort(int[] rawList, int endIndex)
    {
        for (int i = 0; i < endIndex; i++)
            Swap(rawList, i);
        endIndex--;
        return endIndex == 0 ? rawList.ToList() : BubbleSort(rawList, endIndex);
    }

View Code

希尔排序：希尔排序本质上就是(选择排序或冒泡或插入)，它先对第1,1+n,1+2n,1+3n...看作一个队列并排序，然后2,2+n,2+2n,2+3n....排完后将n缩小一倍重复刚才的操作，直至n=1；子队列的排序可以用上述方法。

    public static List<int> ShellSort(int[] rawList)
    {
        int step = rawList.Length / 2;
        List<int> temp = new List<int>();
        while (step > 0)
        {
            for (int j = 0; j < step; j++)
            {
                temp.Clear();
                for (int i = j; i < rawList.Length; i = i + step)
                {
                    temp.Add(rawList[i]);
                }
                temp = InsertSort(temp.ToArray());
                for (int i = j; i < rawList.Length; i = i + step)
                {
                    rawList[i] = temp[i / step];
                }
            }
            step /= 2;
        }
        return rawList.ToList();
    }

View Code

 

标签：rawList,temp,index,C#,List,int,冒泡,排序
From： https://www.cnblogs.com/cfsl/p/16994884.html