常见的几种算法排序（C#）

本文介绍: 总结下常见的几种排序及其实现，帮助自己加深记忆。

总结下常见的几种排序及其实现，帮助自己加深记忆。

1、原理： 通过依次比较相邻的元素，将较大（或较小）的元素交换到右侧，直到整个序列有序。

 public static int[] BuddleSort(int[] arry)
    { 
        int n= arry.Length;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n - 1 - i; j++)
            {
                if (arry[j] < arry[j + 1])
                { 
                    int temp = arry[j];
                    arry[j] = arry[j + 1];
                    arry[j + 1]= temp;
                }
            }
        }
        return arry;
    }

2、算法步骤：
冒泡排序的基本步骤：
（1）遍历数组：从第一个元素开始，依次比较相邻的两个元素。
（2）比较相邻元素：比较当前元素和下一个元素的大小关系。
（3）交换位置：如果当前元素大于下一个元素（升序排序），则交换它们的位置，否则不做任何操作。
（4）遍历次数：完成一轮遍历后，最大（或最小）的元素就会沉到数组的最后一个位置。
（5）重复步骤：重复执行以上步骤，直到数组中的所有元素都已经排序完成。

3、举例：
冒泡排序的每个步骤涉及多次比较和可能的交换操作。这里是对数组 [65, 24, 12, 32, 4, 15] 进行冒泡排序时的每个步骤的输出：
初始数组：[65, 24, 12, 32, 4, 15]
第1次内循环执行后：[24, 12, 32, 4, 15, 65]
第2次内循环执行后：[12, 24, 4, 15, 32, 65]
第3次内循环执行后：[12, 4, 15, 24, 32, 65]
第4次内循环执行后：[4, 12, 15, 24, 32, 65]
第5次内循环执行后：[4, 12, 15, 24, 32, 65]
因此，经过选择排序算法的执行后，数组变为 [4, 12, 15, 24, 32, 65]。
4、时间复杂度
冒泡排序的时间复杂度为 O(n^2)。

1、原理： 每次从未排序的部分选择最小（或最大）的元素，放到已排序部分的末尾，直到整个序列有序。

public static int[] SelectSort(int[] arry)
    {
        int n = arry.Length;
        int temp;
        for (int i = 0; i < n - 1; i++)
        {
            int minIndex = i;
            for (int j = i+1; j < n - 1 ; j++)
            {
                if(arry[j]<arry[minIndex])
                    minIndex = j;                     
            }
            temp = arry[i];
            arry[i] = arry[minIndex];
            arry[minIndex] = temp;
        }

        return arry;
    }

2、算法步骤：
首先，找到数组中最小的元素，并将其与数组的第一个元素交换位置。
接下来，在剩余的未排序部分中找到最小的元素，并将其与数组的第二个元素交换位置。
以此类推，直到所有元素都被排序。

 public static int[] InsertSort(int[] arry)
    {
        int n=arry.Length;
        for (int i = 1; i < n; i++)
        {
            int key = arry[i];
            int j = i - 1;
            while (j >= 0 && key > arry[j]) 
            {
                arry[j+1]=arry[j];
                j--;
            }
            arry[j+ 1] = key;
        }
        return arry;
    }

 public static int[] InsertSort2(int[] arry)
    {
        int n = arry.Length;
        for (int i = 1; i < n; i++)
        {
            int key = arry[i];
            int j = i - 1;
            while (j >= 0 && key > arry[j])
            {
                arry[j+1] = arry[j];
                arry[j]= key;
                j--;
            }
        }
        return arry;
    }

public static int[] QuickSort(int[] arry,int low, int high)
    {
        if (low < high)
        { 
            int pivot =Partition(arry,low,high);
            QuickSort(arry,low,pivot-1);
            QuickSort(arry, pivot+1, high);
        }
        return arry;
    }

 public static int Partition(int[] arry, int low, int high)
    {
        int pivot = arry[low]; // 将第一个元素作为基准元素

        while (low < high)
        {
            // 从右向左找到一个小于基准元素的值
            while (low < high && arry[high] >= pivot)
            {
                high--;
            }
            // 将这个小于基准元素的值放到左侧
            arry[low] = arry[high];

            // 从左向右找到一个大于基准元素的值
            while (low < high && arry[low] <= pivot)
            {
                low++;
            }
            // 将这个大于基准元素的值放到右侧
            arry[high] = arry[low];
        }

        // 将基准元素放到正确的位置上
        arry[low] = pivot;

        // 返回基准元素的索引
        return low;
    }