首页 > 编程语言 >算法入门：排序算法

算法入门：排序算法

时间：2024-02-03 15:45:51浏览次数：28  
标签：arr 入门 int 元素 算法 数组 array 排序

文章目录

1.冒泡排序 2.选择排序 3.插入排序 4.希尔排序 5.归并排序 6.快速排序 7.堆排序  

1.冒泡排序

思想：

  1. 比较相邻元素： 从数组的第一个元素开始，比较相邻的两个元素，如果它们的顺序不对（比如前面的元素大于后面的元素），则交换它们的位置。

  2. 一轮遍历： 一轮比较和可能的交换后，最大的元素就会沉到数组的末尾（类似气泡冒到水面一样，因此得名冒泡排序）。这样，在第一轮遍历结束时，数组的最后一个元素已经是最大的。

  3. 重复遍历： 重复以上的步骤，每一轮都会将当前未排序部分的最大元素放到正确的位置。每一轮遍历后，未排序部分的最大元素都会被确定，不再参与下一轮的比较。

  4. 直到有序： 重复进行比较和交换，直到整个数组有序。在每一轮遍历中，最大的元素都会沉到最后，所以需要进行 n-1 轮遍历，其中 n 是数组的长度。

using System;

class Program
{
    static void Main()
    {
        // 创建一个整数数组
        int[] array = { 64, 34, 25, 12, 22, 11, 90 };

        Console.WriteLine("原始数组：");
        PrintArray(array);

        // 调用冒泡排序算法
        BubbleSort(array);

        Console.WriteLine("\n排序后的数组：");
        PrintArray(array);
    }

    // 冒泡排序算法
    static void BubbleSort(int[] arr)
    {
        int n = arr.Length;

        // 外层循环控制总共需要多少轮遍历
        for (int i = 0; i < n - 1; i++)
        {
            // 内层循环控制每一轮遍历中的元素比较和交换
            for (int j = 0; j < n - i - 1; j++)
            {
                // 如果当前元素大于下一个元素，则交换它们
                if (arr[j] > arr[j + 1])
                {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    // 打印数组元素
    static void PrintArray(int[] arr)
    {
        foreach (var item in arr)
        {
            Console.Write(item + " ");
        }
        Console.WriteLine();
    }
}

  • BubbleSort方法： 内含两层嵌套的循环，外层循环控制总共需要多少轮遍历，内层循环控制每一轮遍历中的元素比较和交换。在每一轮内层循环中，比较相邻的两个元素，如果它们的顺序不对就交换。这个过程重复进行，直到整个数组有序。

  • PrintArray方法： 用于打印数组元素。

这个算法的时间复杂度是O(n^2)，其中 n 是数组的长度。冒泡排序是一种比较慢的排序算法，但由于其简单易懂的原理，通常用于教学和理解排序算法的基本思想。在实际应用中，对于大规模数据，更高效的排序算法（如快速排序、归并排序等）通常更为适用。

 

2.选择排序

思想：

  1. 找到最小元素： 首先，从待排序的数组中找到最小的元素，并将其放在数组的起始位置。

  2. 遍历未排序部分： 然后，在未排序部分继续寻找最小元素，将其放在已排序部分的末尾。

  3. 交换位置： 交换找到的最小元素与未排序部分的第一个元素，确保最小元素被放置在正确的位置。

  4. 重复遍历： 重复以上步骤，每一轮都会在未排序的部分找到最小的元素，并将其交换到已排序部分的末尾。

  5. 直到有序： 继续进行上述过程，直到整个数组都有序。每一轮遍历都会确定未排序部分的最小元素，并将其添加到已排序部分的末尾。

using System;

class Program
{
    static void Main()
    {
        // 创建一个整数数组
        int[] array = { 64, 34, 25, 12, 22, 11, 90 };

        Console.WriteLine("原始数组：");
        PrintArray(array);

        // 调用选择排序算法
        SelectionSort(array);

        Console.WriteLine("\n排序后的数组：");
        PrintArray(array);
    }

    // 选择排序算法
    static void SelectionSort(int[] arr)
    {
        int n = arr.Length;

        // 外层循环控制总共需要多少轮遍历
        for (int i = 0; i < n - 1; i++)
        {
            // 假设未排序部分的第一个元素是最小的
            int minIndex = i;

            // 内层循环找到未排序部分的最小元素的索引
            for (int j = i + 1; j < n; j++)
            {
                // 如果当前元素比最小元素小，则更新最小元素的索引
                if (arr[j] < arr[minIndex])
                {
                    minIndex = j;
                }
            }

            // 将最小元素与未排序部分的第一个元素交换位置
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

    // 打印数组元素
    static void PrintArray(int[] arr)
    {
        foreach (var item in arr)
        {
            Console.Write(item + " ");
        }
        Console.WriteLine();
    }
}

  • SelectionSort方法： 外层循环控制总共需要多少轮遍历，内层循环用于找到未排序部分的最小元素的索引。在每一轮内层循环中，假设未排序部分的第一个元素是最小的，然后通过遍历找到更小的元素的索引。最后，将找到的最小元素与未排序部分的第一个元素进行交换。

  • PrintArray方法： 用于打印数组元素。

选择排序的时间复杂度是O(n^2)，其中 n 是数组的长度。虽然选择排序在性能上不如一些更高级的排序算法，但由于其简单性，通常用于教学和理解排序算法的基本思想。在实际应用中，对于大规模数据，更高效的排序算法通常更为适用。

 

3.插入排序

思想：将待排序的数组分为已排序和未排序两部分，初始时已排序部分只包含第一个元素。然后，逐步将未排序部分的元素插入到已排序部分的正确位置，直到整个数组有序。

  1. 初始化： 将第一个元素看作已排序部分，其余元素看作未排序部分。

  2. 逐步插入： 从未排序部分选择一个元素，与已排序部分的元素逐一比较，找到插入位置。将该元素插入到已排序部分的合适位置，使得已排序部分依然有序。

  3. ： 重复以上步骤，每次选择未排序部分的第一个元素，插入到已排序部分，直到整个数组有序。

using System;

class Program
{
    static void Main()
    {
        // 创建一个整数数组
        int[] array = { 64, 34, 25, 12, 22, 11, 90 };

        Console.WriteLine("原始数组：");
        PrintArray(array);

        // 调用插入排序算法
        InsertionSort(array);

        Console.WriteLine("\n排序后的数组：");
        PrintArray(array);
    }

    // 插入排序算法
    static void InsertionSort(int[] arr)
    {
        int n = arr.Length;

        // 外层循环从第二个元素开始，将其插入到已排序部分的正确位置
        for (int i = 1; i < n; i++)
        {
            int key = arr[i];
            int j = i - 1;

            // 内层循环将未排序部分的元素插入到已排序部分的正确位置
            while (j >= 0 && arr[j] > key)
            {
                arr[j + 1] = arr[j];
                j = j - 1;
            }

            arr[j + 1] = key;
        }
    }

    // 打印数组元素
    static void PrintArray(int[] arr)
    {
        foreach (var item in arr)
        {
            Console.Write(item + " ");
        }
        Console.WriteLine();
    }
}

  • InsertionSort方法： 外层循环从数组的第二个元素开始，将其插入到已排序部分的正确位置。内层循环负责将未排序部分的元素插入到已排序部分的正确位置。具体地，将未排序部分的元素与已排序部分的元素逐一比较，找到插入位置，并依次移动已排序部分的元素。

  • PrintArray方法： 用于打印数组元素。

插入排序的时间复杂度是O(n^2)，其中 n 是数组的长度。虽然插入排序在处理部分有序的数组时性能较好，但对于大规模数据，更高效的排序算法通常更为适用。插入排序在实现上比冒泡排序和选择排序稍微复杂，但相对而言，它对于小规模数据或者已经部分有序的数据表现较好。

 

4.希尔排序

思路：希尔排序是插入排序的一种改进版本，它通过比较相隔一定间隔的元素，并逐步减小这个间隔，最终完成排序。通过比较和交换距离较远的元素，可以将较小的元素快速移动到合适的位置。这样，在最后一轮插入排序时，需要移动的元素数量相对较小，提高了排序的效率。

  1. 确定间隔序列： 选择一个递减的间隔序列（例如，Knuth序列或者Sedgewick序列）。

  2. 按间隔分组： 将数组按照间隔分成多个子序列，对每个子序列进行插入排序。

  3. 逐步缩小间隔： 逐步减小间隔，重复进行插入排序，直到最终间隔为1。

  4. 最后排序： 当间隔为1时，进行最后一次插入排序，此时数组基本有序。

using System;

class Program
{
    static void Main()
    {
        // 创建一个整数数组
        int[] array = { 64, 34, 25, 12, 22, 11, 90 };

        Console.WriteLine("原始数组：");
        PrintArray(array);

        // 调用希尔排序算法
        ShellSort(array);

        Console.WriteLine("\n排序后的数组：");
        PrintArray(array);
    }

    // 希尔排序算法
    static void ShellSort(int[] arr)
    {
        int n = arr.Length;

        // 计算初始间隔，可以选择不同的间隔序列
        int gap = n / 2;

        // 外层循环，逐步减小间隔
        while (gap > 0)
        {
            // 内层循环，对每个子序列进行插入排序
            for (int i = gap; i < n; i++)
            {
                int temp = arr[i];
                int j = i;

                // 对子序列进行插入排序
                while (j >= gap && arr[j - gap] > temp)
                {
                    arr[j] = arr[j - gap];
                    j = j - gap;
                }

                arr[j] = temp;
            }

            // 缩小间隔
            gap = gap / 2;
        }
    }

    // 打印数组元素
    static void PrintArray(int[] arr)
    {
        foreach (var item in arr)
        {
            Console.Write(item + " ");
        }
        Console.WriteLine();
    }
}

  • ShellSort方法： 使用希尔排序算法。外层循环逐步减小间隔，内层循环对每个子序列进行插入排序。在插入排序中，通过比较和移动元素，将较小的元素逐步移到合适的位置。

  • PrintArray方法： 用于打印数组元素。

希尔排序使用初始间隔为数组长度的一半，然后逐步缩小间隔。不同的间隔序列可能影响排序性能，可以根据具体情况选择不同的序列。希尔排序相对于简单的插入排序，在大规模数据的排序中性能上有一定提升。

 

5.归并排序

思路：归并排序（Merge Sort）是一种分治策略的排序算法，它的基本思路是将一个大问题拆分成小问题，分别解决小问题，然后将小问题的解合并起来，最终得到整体的解。

  1. 拆分阶段： 将待排序的数组递归地拆分为两个子数组，直到每个子数组只包含一个元素。

  2. 排序阶段： 对每一对子数组进行排序，可以使用递归进行排序。

  3. 合并阶段： 将排好序的子数组合并成一个更大的有序数组。

  4. 重复合并： 重复以上步骤，直到整个数组有序。

using System;

class Program
{
    static void Main()
    {
        // 创建一个整数数组
        int[] array = { 64, 34, 25, 12, 22, 11, 90 };

        Console.WriteLine("原始数组：");
        PrintArray(array);

        // 调用归并排序算法
        MergeSort(array);

        Console.WriteLine("\n排序后的数组：");
        PrintArray(array);
    }

    // 归并排序算法
    static void MergeSort(int[] arr)
    {
        int n = arr.Length;

        // 如果数组长度小于等于1，已经有序
        if (n <= 1)
            return;

        // 计算中间索引
        int mid = n / 2;

        // 创建左右子数组
        int[] left = new int[mid];
        int[] right = new int[n - mid];

        // 将元素分配到左右子数组
        for (int i = 0; i < mid; i++)
            left[i] = arr[i];

        for (int i = mid; i < n; i++)
            right[i - mid] = arr[i];

        // 递归对左右子数组进行归并排序
        MergeSort(left);
        MergeSort(right);

        // 合并左右子数组
        Merge(arr, left, right);
    }

    // 合并两个有序数组
    static void Merge(int[] arr, int[] left, int[] right)
    {
        int nLeft = left.Length;
        int nRight = right.Length;
        int i = 0, j = 0, k = 0;

        // 比较左右子数组的元素，合并到原数组
        while (i < nLeft && j < nRight)
        {
            if (left[i] <= right[j])
            {
                arr[k] = left[i];
                i++;
            }
            else
            {
                arr[k] = right[j];
                j++;
            }
            k++;
        }

        // 将左子数组的剩余元素添加到原数组
        while (i < nLeft)
        {
            arr[k] = left[i];
            i++;
            k++;
        }

        // 将右子数组的剩余元素添加到原数组
        while (j < nRight)
        {
            arr[k] = right[j];
            j++;
            k++;
        }
    }

    // 打印数组元素
    static void PrintArray(int[] arr)
    {
        foreach (var item in arr)
        {
            Console.Write(item + " ");
        }
        Console.WriteLine();
    }
}

  • MergeSort方法： 递归拆分数组并调用Merge方法进行合并。在拆分阶段，将数组拆分成左右两个子数组，然后递归对左右子数组进行排序。在合并阶段，调用Merge方法将排好序的左右子数组合并到原数组中。

  • Merge方法： 合并两个有序数组。该方法接受一个原数组和两个有序的子数组（左子数组和右子数组），然后按照顺序将它们合并到原数组中。

  • PrintArray方法： 用于打印数组元素。

归并排序是一种稳定的排序算法，它的时间复杂度是O(n log n)。尽管归并排序在性能上相对较好，但由于需要额外的空间来存储中间结果，可能在空间复杂度上相对较高。

 

6.快速排序

思路：快速排序是一种基于分治策略的排序算法，它的基本思路是选择一个元素作为“基准”（pivot），将数组划分为两个子数组，左边的子数组包含所有小于基准的元素，右边的子数组包含所有大于基准的元素，然后对左右子数组分别递归地进行快速排序。

  1. 选择基准： 从数组中选择一个元素作为基准。

  2. 划分阶段： 将数组中小于基准的元素放到基准的左侧，大于基准的元素放到右侧。

  3. 递归排序： 对基准左右两侧的子数组分别递归地进行快速排序。

  4. 合并结果： 不需要合并操作，因为划分阶段已经将数组原地排序。

using System;

class Program
{
    static void Main()
    {
        // 创建一个整数数组
        int[] array = { 64, 34, 25, 12, 22, 11, 90 };

        Console.WriteLine("原始数组：");
        PrintArray(array);

        // 调用快速排序算法
        QuickSort(array, 0, array.Length - 1);

        Console.WriteLine("\n排序后的数组：");
        PrintArray(array);
    }

    // 快速排序算法
    static void QuickSort(int[] arr, int low, int high)
    {
        if (low < high)
        {
            // 划分阶段，获取基准的位置
            int pivotIndex = Partition(arr, low, high);

            // 递归排序左右子数组
            QuickSort(arr, low, pivotIndex - 1);
            QuickSort(arr, pivotIndex + 1, high);
        }
    }

    // 划分阶段
    static int Partition(int[] arr, int low, int high)
    {
        // 选择基准元素
        int pivot = arr[high];
        int i = low - 1;

        // 将小于基准的元素放到左侧，大于基准的元素放到右侧
        for (int j = low; j < high; j++)
        {
            if (arr[j] <= pivot)
            {
                i++;
                Swap(arr, i, j);
            }
        }

        // 将基准元素放到正确的位置
        Swap(arr, i + 1, high);

        return i + 1;
    }

    // 交换数组中两个元素的位置
    static void Swap(int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 打印数组元素
    static void PrintArray(int[] arr)
    {
        foreach (var item in arr)
        {
            Console.Write(item + " ");
        }
        Console.WriteLine();
    }
}

  • QuickSort方法： 快速排序的入口，递归地进行快速排序。在每一次递归中，通过调用Partition方法进行划分阶段。

  • Partition方法： 划分阶段的实现。选择基准元素，将小于基准的元素放到左侧，大于基准的元素放到右侧。最后将基准元素放到正确的位置。

  • Swap方法： 用于交换数组中两个元素的位置。

  • PrintArray方法： 用于打印数组元素。

快速排序的时间复杂度为O(n log n)，其中 n 是数组的长度。它是一种不稳定的排序算法，通常在实际应用中对于大规模数据的排序性能较好。

 

7.堆排序

思路：堆排序是一种基于二叉堆的排序算法，它的基本思路是首先将待排序的数组构建成一个二叉堆（最大堆或最小堆），然后进行堆的删除操作，每次删除堆顶元素，将其放入已排序部分，然后对剩余元素重新构建堆，重复这个过程，直到整个数组有序。

  1. 构建堆： 将待排序的数组构建成一个二叉堆。可以选择构建最大堆或最小堆，这里以构建最大堆为例。

  2. 堆排序： 依次将堆顶元素与堆的最后一个元素交换，将堆的大小减少1，并重新调整堆，使其满足最大堆的性质。

  3. 重复步骤2： 重复步骤2，直到整个数组有序。

using System;

class Program
{
    static void Main()
    {
        // 创建一个整数数组
        int[] array = { 64, 34, 25, 12, 22, 11, 90 };

        Console.WriteLine("原始数组：");
        PrintArray(array);

        // 调用堆排序算法
        HeapSort(array);

        Console.WriteLine("\n排序后的数组：");
        PrintArray(array);
    }

    // 堆排序算法
    static void HeapSort(int[] arr)
    {
        int n = arr.Length;

        // 构建最大堆
        BuildMaxHeap(arr);

        // 堆排序
        for (int i = n - 1; i > 0; i--)
        {
            // 将堆顶元素与堆的最后一个元素交换
            Swap(arr, 0, i);

            // 重新调整堆，保持最大堆的性质
            Heapify(arr, i, 0);
        }
    }

    // 构建最大堆
    static void BuildMaxHeap(int[] arr)
    {
        int n = arr.Length;

        // 从最后一个非叶子节点开始，依次向前调整堆
        for (int i = n / 2 - 1; i >= 0; i--)
        {
            Heapify(arr, n, i);
        }
    }

    // 调整堆，保持最大堆的性质
    static void Heapify(int[] arr, int n, int i)
    {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        // 比较根节点、左子节点和右子节点，找到最大值的索引
        if (left < n && arr[left] > arr[largest])
        {
            largest = left;
        }

        if (right < n && arr[right] > arr[largest])
        {
            largest = right;
        }

        // 如果最大值不是根节点，则交换并继续调整
        if (largest != i)
        {
            Swap(arr, i, largest);
            Heapify(arr, n, largest);
        }
    }

    // 交换数组中两个元素的位置
    static void Swap(int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 打印数组元素
    static void PrintArray(int[] arr)
    {
        foreach (var item in arr)
        {
            Console.Write(item + " ");
        }
        Console.WriteLine();
    }
}

  • HeapSort方法： 堆排序的入口，首先调用BuildMaxHeap方法构建最大堆，然后进行堆排序。在堆排序中，每次将堆顶元素与堆的最后一个元素交换，然后重新调整堆。

  • BuildMaxHeap方法： 构建最大堆的方法，从最后一个非叶子节点开始，依次向前调整堆。

  • Heapify方法： 调整堆的方法，用于保持最大堆的性质。

  • Swap方法： 用于交换数组中两个元素的位置。

  • PrintArray方法： 用于打印数组元素。

堆排序的时间复杂度为O(n log n)，其中 n 是数组的长度。堆排序是一种不稳定的排序算法，适用于大规模数据的排序。

 

标签：arr,入门,int,元素,算法,数组,array,排序
From： https://www.cnblogs.com/hxjcore/p/17973030

相关文章

  • 基础算法（十）差分模板---以题为例
    输入一个长度为 n的整数序列。接下来输入 m个操作，每个操作包含三个整数 l,r,c，表示将序列中 [l,r]之间的每个数加上 c。请你输出进行完所有操作后的序列。输入格式第一行包含两个整数 n 和 m。第二行包含 n 个整数，表示整数序列。接下来 m 行，每行包含三个整数 l，r......
  • 抢红包随机金额算法（均衡随机）
    最优算法在文末，欢迎参考。编写抢红包随机算法功能，通常金额是红包支付后立马算好的，而不是抢一个实时随机一个红包金额，避免并发情况下降低性能。需求仿照微信发红包功能，现有n个人抢金额为m的红包，m>=0.01，n>0，m/n不能小于0.01，需保证每个人都能抢到最低为0.01的金额，金额随机，但金额相......
  • 基础算法（九）二维前缀和模板---以题为例
    输入一个 n 行 m的整数矩阵，再输入q 个询问，每个询问包含四个整数 x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。对于每个询问输出子矩阵中所有数的和。输入格式第一行包含三个整数 n，m，q。接下来 n行，每行包含m 个整数，表示整数矩阵。接下来 q 行，每行包含四个......
  • 基础算法（八）前缀和模板---以前缀和题目为例
    题目如下输入一个长度为 n的整数序列。接下来再输入 m个询问，每个询问输入一对 l,r。对于每个询问，输出原序列中从第 l 个数到第 r个数的和。输入格式第一行包含两个整数 n 和 m。第二行包含 n 个整数，表示整数数列。接下来 m 行，每行包含两个整数 l 和 r，......
  • （坚持每天写算法）算法学习与复习part1基础算法1-13——位运算
    最近确实有在写算法，在写dp，之前学的时候不全，被计数，树型等dp折磨了一下。位运算是将重点放在数字的位上，通常作为辅助行动，比如状态dp，有的时候是为了节省时空复杂度而使用的。这是今天的题目： 位运算应用的情况除了上面讲的，还有单纯的位问题，上面的题目就是一个例......
  • 【优先级调度算法：抢占式与非抢占式】
    (文章目录)前言在操作系统中，进程调度决定了哪个进程应该获得CPU的使用权，以便能够执行。而优先级调度算法就是其中之一，它通过为每个进程分配一个优先级来决定进程的执行顺序。什么是优先级调度算法？优先级调度算法是一种用于确定哪个进程将在CPU上执行的方法。每个进程都会被分配......
  • 第十五节：排序算法详解3(希尔排序、计数排序、桶排序、基数排序)
    一.        二.        三.         !作       者:Yaopengfei(姚鹏飞)博客地址:http://www.cnblogs.com/yaopengfei/声     明1:如有错误，欢迎讨论，请勿谩骂^_^。声     明2:原创博客请在转载......
  • 算法学习
    今天学习了约数的个数怎么求，一般的算法会超时。这时我们需要用到一个定理：p=[n/i]：表示在[1,n]的区间内，有约数i的个数为p个。所以这时，在求约数个数的问题上，我们只需要遍历[1,n]，设置一个计数器即可。当n很大时，跨越太大，这时i++、就会很慢，设置j=n/(n/i)+1;下一次让i=j;这样跨度较......
  • 基础模板/算法
    线性筛求素数#include<bits/stdc++.h>usingnamespacestd;constintN=5e7+50;intn,tot,prime[N];//prime存储所有素数boolflag[N];//判断是否为素数intmain(){scanf("%d",&n);//初始化，flag全部置为truefor(inti=1;i<=n;i++)fl......
  • [转帖]SQL SERVER--- 排序规则、数据类型
    https://zhuanlan.zhihu.com/p/162933497 一、排序规则有时候我们向数据库插入文本时，会出现乱码“?”，这时有可能是我们创建数据库没有设置好排序规则以Chinese_PRC_CI_AS为例前半部分Chinese_PRC指的是针对大陆简体字unicode的排序规则后半部分的含义为：_BIN二进......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99