前言

大家好，这是自己整理的C#常见排序算法笔记，方便自己学习的同时分享出来，感谢支持。

1. 冒泡排序

• 重复遍历数组比较相邻的元素,如果前面的比后面的大,就交换它们两个
• 每次遍历整个数组,遍历完成后,下一次遍历的索引减一（范围往左缩一位）
• 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较，则排序完成

1.1 动态展示：

1.2 算法实现：

public class Solution
{
    // 冒泡排序   
    static void bubbleSort(int[] nums)
    {
        int n = nums.Length;    // 得到数组的长度     
        for (int i = 0; i < n; i++)
        {
            bool flag = false;      // 表示本轮是否有进行变量交换
            for (int idx = 0; idx < n - i - 1; idx++)
            {
                if (nums[idx] > nums[idx + 1])
                {
                    int temp = nums[idx];
                    nums[idx] = nums[idx + 1];
                    nums[idx + 1] = temp;
                    flag = true;
                }
            }
            // 如果flag为False,那说明本轮排序没有进行任何变量交换
            // 数组已经是有序的了
            if (!flag)
            {
                break;
            }
        }
    }

    static void Main()
    {
        int[] test = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
        bubbleSort(test);

        foreach (int item in test)
        {
            Console.WriteLine(item);
        }
    }
}

2. 选择排序

• 数组的初始状态：有序区为空，无序区为[0,…,n]
• 每次找到无序区里的最小元素，添加到有序区的最后
• 重复前面步骤，直到整个数组排序完成

2.1 动态展示：

2.2 算法实现：

public class Solution
{
    // 选择排序 
    public static void selectionSort(int[] nums)
    {
        int n = nums.Length;
        for (int i = 0; i < n; i++)
        {
            // 找无序区中最小的元素 
            int minIndex = i;  //无序区中的最小元素的索引
            for (int j = i + 1; j < n; j++)
            {
                if (nums[j] < nums[minIndex])
                {
                    minIndex = j;
                }
            }
            // 执行完上面的循环后
            // minIndex就是无序区中的最小元素的索引
            // 把最小元素和有序区的后一个元素交换位置
            int temp = nums[i];
            nums[i] = nums[minIndex];
            nums[minIndex] = temp;
        }
    }

    static void Main()
    {
        int[] test = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
        selectionSort(test);
        foreach (int item in test)
        {
            Console.WriteLine(item);
        }
    }
}

3. 插入排序

• 整个数组分为左边部分有序元素集合和右边部分无序元素集合
• 一开始从索引为一的元素开始逐渐递增与有序集合进行比较
• 将未排序的元素一个一个地插入到有序的集合中，插入时把所有有序集合从后向前扫一遍，找到合适的位置插入

3.1 动态展示：

3.2 算法实现：

public class Solution
{
    // 插入排序 
    public static void insertSort(int[] nums)
    {
        int n = nums.Length;     // 数组的长度

        for (int i = 0; i < n - 1; i++)
        {
            int curNum = nums[i + 1];     // 无序区的第一个元素 
            int idx = i;    //有序区的最后一个元素的索引

            while (idx >= 0 && nums[idx] > curNum)
            {
                nums[idx + 1] = nums[idx];  // 把有序区的元素往后挪一位
                idx -= 1;
            }
            nums[idx + 1] = curNum;
        }
    }

    static void Main()
    {
        int[] test = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
        insertSort(test);
        foreach (int item in test)
        {
            Console.WriteLine(item);
        }
    }
}

4. 快速排序

• 开始设定一个基准值pivot
• 将数组重新排列，所有比pivot小的放在其前面，比pivot大的放后面，这种操作称为分区(partition)操作
• 对两边的数组重复前两个步骤; （分而治之算法思想）

4.1 动态展示：

4.2 算法实现：

public class Solution
{
    // 分区
    public static int partition(int[] nums, int left, int right)
    {
        int pivot = nums[left];     // 区域的第一个元素作为基准值

        while (left < right)
        {
            while (left < right && nums[right] > pivot)
                right--;
            nums[left] = nums[right];

            while (left < right && nums[left] <= pivot)
                left++;
            nums[right] = nums[left];
        }
        nums[right] = pivot;        // 基准值的正确位置 

        return left;        // 返回基准值 
    }

    // 快速排序 
    public static void quickSort(int[] nums, int left, int right)
    {
        if (left >= right)
            return;

        // 分区 --> 分好区之后的基准值的索引 
        int pivotIndex = partition(nums, left, right);
        // 左边的区域, left -> pivotIndex - 1 
        quickSort(nums, left, pivotIndex - 1);
        // 右边的区域，pivotIndex+1->right 
        quickSort(nums, pivotIndex + 1, right);
    }


    static void Main()
    {
        int[] test = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
        quickSort(test, 0, test.Length - 1);
        foreach (int item in test)
        {
            Console.WriteLine(item);
        }
    }
}

5. 随机快速排序

• 将一个待排序的数组随机选择“基准”（pivot）分割成两个独立的子数组
• 其中一部分的所有元素都比另外一部分的所有元素都要小
• 按此方法对这两部分元素分别进行快速排序
• 整个排序过程可以递归进行，以此达到整个数据变成有序序列

5.1 动态展示：

5.2 算法实现：

public class Solution
{
    // 随机分区 
    public static int randomPartition(int[] nums, int left, int right)
    {
        Random random = new Random();   // 随机生成数 
        int i = random.Next(left,right);
        int temp = nums[i];
        nums[i] = nums[right];
        nums[right] = nums[i];

        return partition(nums, left, right); 
    }

    // 分区 
    public static int partition(int[] nums, int left, int right)
    {
        int pivot = nums[left];     // 区域的第一个元素作为基准值

        while(left < right)
        {
            while (left < right && nums[right] > pivot)
                right--;
            nums[left] = nums[right];
                                    
            while (left < right && nums[left] <= pivot)
                left++;
            nums[right] = nums[left];
        }
        nums[right] = pivot;        // 基准值的正确位置 

        return left;        // 返回基准值 
    }

    // 快速排序 
    public static void quickSort(int[] nums, int left, int right)
    {
        if (left >= right)
            return; 

        // 分区 --> 分好区之后的基准值的索引 
        int pivotIndex = randomPartition(nums, left, right);
        // 左边的区域, left -> pivotIndex - 1 
        quickSort(nums, left, pivotIndex - 1);
        // 右边的区域，pivotIndex+1->right 
        quickSort(nums, pivotIndex+1, right);  
    }


    static void Main()
    {
        int[] test = { 44, 12, 59, 36, 62, 43, 94, 7, 35, 52, 85 };
        quickSort(test, 0, test.Length-1); 
        foreach(int item in test)
        {
            Console.WriteLine(item);
        }
    }
}

6. 归并排序

• 归并排序算法是采用分治法的一个非常典型的应用
• 不断将数组一分为二，一直分到子数组的长度小于等于一（无法再分）
• 通过递归的方法逐个比较大小自底向上有序地合并数组

6.1 动态展示：

6.2 算法实现：

public class Solution
{
    // 合并
    public static int[] merge(int[] left, int[] right)
    {
        // 最终返回一个合并好的有序的数组
        // 定义两个变量,分别代表当前left与right的未添加进有序数组的第一个元素
        int leftIndex = 0, rightIndex = 0;
        List<int> res = new List<int>();        
       
        while (leftIndex < left.Length && rightIndex < right.Length)
        {
            //左边数组的元素小于右边数组 
            if (left[leftIndex] <= right[rightIndex])
            {
                // 把左边元素添加到有序区中 
                res.Add(left[leftIndex]);
                // 索引往后移
                leftIndex ++; 
            }
            else
            {
                // 把右边元素添加到有序区中 
                res.Add(right[rightIndex]);
                // 索引往后移 
                rightIndex ++; 
            }
        }

        // 把剩余的未添加的元素全部添加到有序数组后面
        foreach (int item in right[rightIndex..])    
        {
            res.Add(item);
        }

        // 为什么可以直接添加?因为left,right本身就是一个有序数组
        foreach (int item in left[leftIndex..])      
        {
            res.Add(item);
        }
        // 如果说left_idx走完了,right还剩一些元素,说明right剩下的元素全部都比有序数组的最后一个元素要大
        return res.ToArray();
    }

    // 归并排序
    public static int[] mergeSort(int[] nums)
    {
        //数组不能再分了
        if (nums.Length <= 1)
            return nums;
        int mid = nums.Length / 2;      // 求出数组的中间位置 
        
        int[] left = mergeSort(nums[..mid]);
        int[] right = mergeSort(nums[mid..]);
   
        // 合并
        return merge(left, right); 
    }

    // 归并排序 
    static void Main(string[] args)
    {
        int[] nums = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48}; 
        int[] result = mergeSort(nums);
        foreach(int item in result)
        {
            Console.WriteLine(item);
        }
    }
}

7. 计数排序

• 找出待排序的数组中最大和最小的元素
• 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
• 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
• 向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

7.1 动态展示：

7.2 算法实现：

public class Program
{
    // 计数排序
    public static void CountingSort(int[] array)
    {
        // 长度小于等于0直接return
        if (array.Length <= 0) 
            return;

        int min = array[0];     
        int max = min;
        // 找出数组最大元素和最小元素 
        foreach (int item in array)
        {
            if (item > max)
            {
                max = item;
            }
            else if (item < min)
            {
                min = item;
            }
        }

        // 把所有元素存入counting数组 
        int[] counting = new int[max - min + 1];
        for (int i = 0; i < array.Length; i++)
        {
            counting[array[i] - min] += 1;
        }

        int index = -1;
        for (int i = 0; i < counting.Length; i++)
        {
            for (int j = 0; j < counting[i]; j++)
            {
                index++;
                array[index] = i + min;
            }
        }
    }


    public static void Main(string[] args)
    {
        int[] array = { 43, 69, 11, 72, 28, 21, 56, 80, 48, 94, 32, 8 };
        CountingSort(array);

        foreach(int item in array)
        {
            Console.WriteLine(item);
        }
    } 
}

8. 基数排序

• 基数排序是一种非比较型排序和利用桶的算法，直接利用每个位数作为下标放入桶中，无需与其他元素比较大小
• 将待比较的数字从较低位到较高位依次放入桶中， 再按照桶的顺序取出
• 直到最长位数的数字被完全比较，即可得到已排序的数组

8.1 动态展示：

8.2 算法实现：

public class Program
{
    // 基数排序 
    public static void RadixSort(int[] array, int bucketNum)
    {
        int maxLength = MaxLength(array);

        //创建bucket时，在二维中增加一组标识位，
        //其中bucket[x, 0]表示这一维所包含的数字的个数
        //通过这样的技巧可以少写很多代码
        int[,] bucket = new int[bucketNum, array.Length + 1];

        for (int i = 0; i < maxLength; i++)
        {
            foreach (var num in array)
            {
                int bit = (int)(num / Math.Pow(10, i) % 10);
                bucket[bit, ++bucket[bit, 0]] = num;
            }

            for (int count = 0, j = 0; j < bucketNum; j++)
            {
                for (int k = 1; k <= bucket[j, 0]; k++)
                {
                    array[count++] = bucket[j, k];
                }
            }

            //最后要重置这个标识
            for (int j = 0; j < bucketNum; j++)
            {
                bucket[j, 0] = 0;
            }

        }
    }

    private static int MaxLength(int[] array)
    {
        if (array.Length <= 0) 
            return 0;
            
        int max = array.Max();      // 取出数组的最大值 
        return (int)Math.Log10(max) + 1;    // 取出位数 
    }


    public static void Main(string[] args)
    {
        int[] array = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        RadixSort(array, 10);
        foreach (int item in array)
        {
            Console.WriteLine(item);
        }
    }
}

9. 桶排序

• 桶排序是计数排序的升级版
• 根据数组的最大值与最小值申请一些桶（生成对应的序列）
• 将数组的元素放入桶中，并保证桶里是有序的
• 合并每个桶，得到的就是一个有序的序列

9.1 动态展示：

9.2 算法实现：

public class Program
{
    // 桶排序
    static void BucketSort(int[] array, int bucketsize = 5)
    {
        int max = array.Max(), min = array.Min();               // 最大值与最小值
        int bucketnums = (max - min) / bucketsize + 1;           // 分配的桶数量

        List<List<int>> buckets = new List<List<int>>();
        // 生成桶
        for (int i = 0; i < bucketnums; i++)
        {
            buckets.Add(new List<int>());
        }

        //将数组的元素放入桶中,并保证桶里是有序的        
        for (int i = 0; i < array.Length; i++)
        {
            int bucketIndex = (array[i] - min) / bucketsize;
            buckets[bucketIndex].Add(array[i]);
        }

        int index = 0;
        for (int i = 0; i < buckets.Count; i++)
        {
            buckets[i].Sort();      // 对生成的每个桶排序 
            for (int j = 0; j < buckets[i].Count; j++)
            {
                array[index++] = buckets[i][j];
            }
        }
    }
    
    static void Main(string[] args)
    {
        int[] test = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
        BucketSort(test); 
        
        foreach(int item in test)
        {
            Console.WriteLine(item);
        }
    }
}

10. 堆排序

• 将待排序的数组构造成一个大顶堆，整个数组的最大值就是堆结构的顶端
• 将顶端的数与末尾的数交换，则末尾的数为最大值，剩余待排序数组个数为n-1（n为数组长度）
• 将剩余的n-1个数再构造成大根堆，再将顶端数与n-1位置的数交换，如此反复执行，便能得到有序数组
• 注意:升序用大根堆，降序就用小根堆(默认为升序)

10.1 动态展示：

10.2 算法实现：

class Program
{
    // 堆排序 
    public static void HeapSort(int[] nums)
    {
        //将最大的值推到堆顶
        //x根据最后一个子节点的位置计算出父节点
        int x = Convert.ToInt32(Math.Floor(Convert.ToDouble((nums.Length - 2) / 2)));
        for (int i = x; i >= 0; i--)
        {
            //如果子元素只存在左子元素时, 让右子元素等于左子元素
            while (nums[i] < nums[i * 2 + 1] || nums[i] < nums[(i * 2 + 2) > (nums.Length - 1) ? (i * 2 + 1) : i * 2 + 2])
            {
                if (nums[i * 2 + 1] >= nums[(i * 2 + 2) > (nums.Length - 1) ? (i * 2 + 1) : i * 2 + 2])
                {
                    int index = nums[i];
                    nums[i] = nums[i * 2 + 1];
                    nums[i * 2 + 1] = index;
                }
                else
                {
                    int index = nums[i];
                    nums[i] = nums[i * 2 + 2];
                    nums[i * 2 + 2] = index;
                }
            }
        }
        //输出堆顶最大的元素
        int max = nums[0];
        nums[0] = nums[nums.Length - 1];
        Console.WriteLine(max);
        //将数组中的最后一个元素删除
        int[] num = new int[nums.Length - 1];
        for (int j = 0; j < nums.Length - 1; j++)
        {
            num[j] = nums[j];
        }

        Adjust(num);
    }


    public static void Adjust(int[] nums)
    {
        if (nums.Length > 1) HeapSort(nums);
        else Console.WriteLine("{0}\t", nums[0]);
    }

    static void Main(string[] args)
    {
        int[] nums = new int[] { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
        Adjust(nums);
    }
}

11. 希尔排序

• 希尔排序是插入排序的优化版本

• 设定一个增量gap,将数组按照gap分组
• 依次对每一组进行插入排序
• 缩小增量gap,重复前两个步骤,直到gap缩小到一,那么最后一次排序就是

插入排序

11.1 动态展示 :

11.2 算法实现 :

public class Program
{
    // 希尔排序 
    public static void shellSort(int[] nums)
    {
        int n = nums.Length;    // 数组的长度 
        int gap = n / 2;    // 设定一个增量gap 
        
        while(gap >= 1)
        {
            // 分组
            for(int i = gap; i < n; i++) 
            {
                int curNum = nums[i];   // 当前要插入的无序区的元素的值
                int idx = i - gap;      // 当前元素所在小组的有序区的最后一个元素的索引 
                while (idx >= 0 && curNum < nums[idx])      // 插入排序
                {
                    nums[idx + gap] = nums[idx];
                    idx -= gap;
                }
                nums[idx+gap] = curNum; 
            }
            gap /= 2;   // 缩小增量 
        }
    }
     
   
    static void Main(string[] args)
    {
        int[] test = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
        shellSort(test); 
        foreach(int item in test)
        {
            Console.WriteLine(item);
        }
    }
}

总结：

注意

本章部分图文内容来源于网站资料和网友提供, 自己整理收集,方便学习参考,版权属于 原作者。