当前位置：首页 > news >正文

十大经典排序算法 - lucky

news 2025/9/14 16:07:40

十大经典排序算法

1、冒泡排序

1）基本思想：

通过对待排序列从前向后（从下标较小的元素开始），依次对相邻两个元素的值进行两两比较，若发现逆序则交换，使值较大的元素逐渐从前移向后面。

2）算法步骤：

假设有一个数组 arr，长度为 n，冒泡排序可以按照以下步骤进行：

1. 外层循环：控制排序的轮数，总共需要比较 `n-1` 轮。
2. 内层循环：负责比较和交换相邻的元素，每轮比较次数逐渐减少。
3. 交换：当 `arr[j] > arr[j+1]` 时，交换这两个元素。

3)代码实现：

import java.util.Scanner;
import java.util.Arrays;public class BubbleSort {public static void bubbleSort(int[] arr) {int n = arr.length;for(int i=0;i<n-1;i++){boolean flag=false;  //标记是否发生交换for(int j=0;j<n-1;j++){if(arr[j]>arr[j+1]){//交换相邻的元素int temp=arr[j];arr[j]=arr[j+1];arr[j+1]=temp;flag=true;    //发生交换}}if(!flag){  //如果 !falg 为true，则没有发生交换，提前结束break;}}}public static void main(String[] args) {
//        int[] arr = {64, 34, 25, 12, 22, 11, 90};Scanner scanner = new Scanner(System.in);//输入数组长度System.out.print("请输入数组的长度：");int n = scanner.nextInt();//创建数组并输入元素int[] arr =new int[n];System.out.println("请输入一组数进行排序：");for(int i=0;i<n;i++){System.out.print("请输入第"+(i+1)+"个元素：");arr[i]=scanner.nextInt();  //读取元素}System.out.println("排序前的数组：");System.out.println(Arrays.toString(arr));bubbleSort(arr);System.out.println("排序后的数组：");System.out.println(Arrays.toString(arr));}}

4)时间复杂度分析：

最优情况（数组本身有序）： O(n)
最坏情况（数组逆序）： O(n²)
平均情况： O(n²)
空间复杂度： O(1)（原地排序）

2、选择排序

1）基本思想：

选择排序（Selection Sort）是一种简单的排序算法。它的基本思想是：首先在未排序的序列中找到最小（或最大）元素，将它与序列的第一个元素交换；然后再从剩余未排序的元素中找到最小（或最大）元素，与序列的第二个元素交换；依此类推，直到所有元素都排序完成。

2）算法步骤：

从待排序的元素中找到最小（或最大）元素。

将其与待排序序列的第一个元素交换位置。

再从剩下的元素中找到最小（或最大）元素，与序列的第二个元素交换。

重复上述过程，直到整个序列排序完成。

3)代码实现：

public class SelectionSort {// 选择排序算法public static void selectionSort(int[] arr) {int n = arr.length;// 外层循环：逐个选定位置for (int i = 0; i < n - 1; i++) {int minIdx = i;  // 假定当前位置的元素是最小的// 内层循环：寻找最小元素的索引for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIdx]) {minIdx = j;  // 更新最小元素的索引}}// 如果最小元素不在当前位置，则交换if (minIdx != i) {int temp = arr[i];arr[i] = arr[minIdx];arr[minIdx] = temp;}}}// 打印数组public static void printArray(int[] arr) {for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}public static void main(String[] args) {int[] arr = {64, 25, 12, 22, 11};System.out.println("原始数组：");printArray(arr);selectionSort(arr);System.out.println("排序后的数组：");printArray(arr);}
}

4)时间复杂度分析：

3、插入排序

1）基本思想：

插入排序是一种简单的排序算法，它的基本思想是：将待排序的元素逐个插入到已排序的部分中。具体地，假设数组的前 i 个元素已经是有序的，那么接下来将第 i+1 个元素插入到这 i 个元素的合适位置，直到整个数组排序完成。

2）算法步骤：

从第二个元素开始，假设第一个元素已经是排好序的。
将当前元素与其前面已经排好序的元素逐一比较，找到合适的位置插入。
每次插入时，已排序部分的元素都会向右移动，直到找到适合插入的位置。
重复以上过程，直到整个数组排序完成。

3）代码实现（Java）：

public class InsertionSort {// 插入排序算法public static void insertionSort(int[] arr) {int n = arr.length;// 从第二个元素开始，逐个插入到已排序部分for (int i = 1; i < n; i++) {int current = arr[i];  // 当前待插入的元素int j = i - 1;// 找到插入位置并将元素右移while (j >= 0 && arr[j] > current) {arr[j + 1] = arr[j];  // 元素右移j--;}arr[j + 1] = current;  // 插入当前元素}}// 打印数组public static void printArray(int[] arr) {for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}public static void main(String[] args) {int[] arr = {64, 25, 12, 22, 11};System.out.println("原始数组：");printArray(arr);insertionSort(arr);System.out.println("排序后的数组：");printArray(arr);}
}

4)时间复杂度分析：

4、希尔排序

1）基本思想：

希尔排序是基于插入排序的一种改进排序算法，它的基本思想是：将整个待排序的序列分成若干个子序列，对每个子序列进行插入排序。随着排序的进行，子序列的间隔逐渐减小，最终当间隔为 1 时，整个序列就被完全排序。希尔排序的核心在于通过较大的步长对序列进行初步的排序，然后逐渐减小步长，提高排序效率。

2）算法步骤：

选择一个增量序列（步长序列），并将数组按这个增量序列划分为多个子序列。
对每个子序列进行插入排序。
减小步长，并对新的子序列进行插入排序，直到步长为 1 时，再对整个数组进行插入排序。

常见的增量序列有：n/2, n/4, ..., 1，也可以使用其他的增量序列，如 Hibbard 增量、Sedgewick 增量等。

3）代码实现（Java）：

public class ShellSort {// 希尔排序算法public static void shellSort(int[] arr) {int n = arr.length;// 选择一个合适的增量序列for (int gap = n / 2; gap > 0; gap /= 2) {  // 步长逐渐减小// 对每个子序列进行插入排序for (int i = gap; i < n; i++) {int current = arr[i];  // 当前待插入的元素int j = i;// 对当前元素所在的子序列进行插入排序while (j >= gap && arr[j - gap] > current) {arr[j] = arr[j - gap];  // 元素向右移动j -= gap;}arr[j] = current;  // 插入当前元素}}}// 打印数组public static void printArray(int[] arr) {for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}public static void main(String[] args) {int[] arr = {64, 25, 12, 22, 11};System.out.println("原始数组：");printArray(arr);shellSort(arr);System.out.println("排序后的数组：");printArray(arr);}
}

4)时间复杂度分析：

5、归并排序

1）基本思想：

归并排序是一种典型的分治算法。其基本思想是：将一个数组分成两半，分别对这两半进行排序，然后再将排好序的两半合并成一个有序的数组。归并排序通过递归的方式将问题分解成子问题，并在合并时进行排序。

具体步骤是：

将数组分成两半。
对每一半递归地进行归并排序。
合并两个已经排好序的子数组，得到最终的有序数组。

归并排序的时间复杂度始终是 O(nlog⁡n)O(n \log n)O(nlogn)，不受数据的初始顺序影响。

2）算法步骤：

将待排序的数组分成两部分。
递归地对每一部分进行排序。
将两部分合并成一个有序数组。

3）代码实现（Java）：

public class MergeSort {// 归并排序算法public static void mergeSort(int[] arr) {if (arr.length < 2) return;  // 如果数组长度小于2，则无需排序int mid = arr.length / 2;  // 找到中间位置int[] left = new int[mid];  // 左半部分int[] right = new int[arr.length - mid];  // 右半部分// 将数组分成两个子数组System.arraycopy(arr, 0, left, 0, mid);System.arraycopy(arr, mid, right, 0, arr.length - mid);// 递归排序左右两部分mergeSort(left);mergeSort(right);// 合并左右两部分merge(arr, left, right);}// 合并两个有序的子数组public static void merge(int[] arr, int[] left, int[] right) {int i = 0, j = 0, k = 0;// 合并过程while (i < left.length && j < right.length) {if (left[i] <= right[j]) {arr[k++] = left[i++];} else {arr[k++] = right[j++];}}// 如果左部分还有剩余，直接复制while (i < left.length) {arr[k++] = left[i++];}// 如果右部分还有剩余，直接复制while (j < right.length) {arr[k++] = right[j++];}}// 打印数组public static void printArray(int[] arr) {for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}public static void main(String[] args) {int[] arr = {64, 25, 12, 22, 11};System.out.println("原始数组：");printArray(arr);mergeSort(arr);System.out.println("排序后的数组：");printArray(arr);}
}

4)时间复杂度分析：

6、快速排序

1）基本思想：

快速排序是一种基于分治法的排序算法。其基本思想是：

从数组中选择一个基准元素（通常选择第一个元素、最后一个元素或随机选择）。
将数组划分为两个子数组：左边子数组包含所有比基准元素小的元素，右边子数组包含所有比基准元素大的元素。
对左边和右边的子数组分别递归地进行排序。
最终，整个数组被排好序。

快速排序的效率依赖于每次划分时基准元素的选择，理想情况下，基准元素将数组均匀划分为两个部分，保证时间复杂度为 O(nlog⁡n)O(n \log n)O(nlogn)。

2）算法步骤：

选择一个基准元素（通常选择数组的第一个元素、最后一个元素或随机选择）。
将数组重新排序，使得所有小于基准元素的元素都排在基准元素的左边，所有大于基准元素的元素都排在基准元素的右边。此时，基准元素在数组中处于最终位置。
递归地对基准元素左侧和右侧的子数组进行快速排序。
重复以上步骤，直到所有子数组的大小为 1 或空数组，排序完成。

3）代码实现（Java）：

public class QuickSort {// 快速排序算法public 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);}}// 划分数组，返回基准元素的索引public static int partition(int[] arr, int low, int high) {int pivot = arr[high];  // 选择基准元素int i = low - 1;  // i 是较小元素的索引for (int j = low; j < high; j++) {// 如果当前元素小于基准元素if (arr[j] < pivot) {i++;  // 增加较小元素的索引// 交换 arr[i] 和 arr[j]int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 将基准元素放到正确的位置int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;return i + 1;  // 返回基准元素的索引}// 打印数组public static void printArray(int[] arr) {for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}public static void main(String[] args) {int[] arr = {64, 25, 12, 22, 11};System.out.println("原始数组：");printArray(arr);quickSort(arr, 0, arr.length - 1);System.out.println("排序后的数组：");printArray(arr);}
}

4)时间复杂度：

7、堆排序

1）基本思想：

堆排序是一种基于堆（Heap）数据结构的排序算法。堆是一种完全二叉树，具有以下性质：

最大堆：每个父节点的值都大于或等于其子节点的值。
最小堆：每个父节点的值都小于或等于其子节点的值。

堆排序的基本思想是：

将待排序的数组构建成一个堆（通常是最大堆）。
将堆顶元素（最大元素）与堆的最后一个元素交换，然后将堆的大小减 1，重新调整堆。
重复上述步骤，直到堆的大小为 1，此时数组已经排好序。

2）算法步骤：

构建最大堆：将输入数据构建成一个最大堆，使得每个父节点都大于或等于其子节点。
交换堆顶元素与最后一个元素：将堆顶元素（最大元素）与堆的最后一个元素交换，然后将堆的大小减小 1。
重新调整堆：重新调整堆，使其符合最大堆的性质。
重复步骤 2 和 3，直到堆的大小为 1。

3）代码实现（Java）：

public class HeapSort {// 堆排序算法public static void heapSort(int[] arr) {int n = arr.length;// 构建最大堆for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}// 一个一个将元素移到已排序部分for (int i = n - 1; i > 0; i--) {// 将堆顶元素与最后一个元素交换int temp = arr[0];arr[0] = arr[i];arr[i] = temp;// 调整堆heapify(arr, i, 0);}}// 调整堆的函数（确保以 i 为根的子树满足最大堆性质）public 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) {int temp = arr[i];arr[i] = arr[largest];arr[largest] = temp;// 递归地调整子堆heapify(arr, n, largest);}}// 打印数组public static void printArray(int[] arr) {for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}public static void main(String[] args) {int[] arr = {64, 25, 12, 22, 11};System.out.println("原始数组：");printArray(arr);heapSort(arr);System.out.println("排序后的数组：");printArray(arr);}
}

4)时间复杂度：

8、计数排序

1）基本思想：

计数排序是一种非比较型排序算法，它的基本思想是通过统计数组中每个元素的出现次数来决定每个元素的位置。它适用于范围有限的整数排序。

具体步骤是：

找出待排序数组中的最大值和最小值。
根据最大值和最小值构建一个计数数组，用来存储每个元素出现的次数。
通过累加计数数组中的值，确定每个元素的最终位置。
将元素放入输出数组中，完成排序。

计数排序的核心思想是利用“计数”来排序，而不是通过比较元素。

2）算法步骤：

确定元素的范围：找出数组中的最大值和最小值，确定计数数组的大小。
构建计数数组：统计数组中每个元素的出现次数。
计算每个元素的累积次数：将计数数组进行累加，得到每个元素应该放置的位置。
生成排序后的数组：根据累积计数数组的值，填充输出数组，得到最终排序结果。

3）代码实现（Java）：

public class CountingSort {// 计数排序算法public static void countingSort(int[] arr) {if (arr.length <= 1) return;  // 如果数组长度小于等于1，不需要排序// 找到数组中的最大值和最小值int max = arr[0];int min = arr[0];for (int i = 1; i < arr.length; i++) {if (arr[i] > max) {max = arr[i];}if (arr[i] < min) {min = arr[i];}}// 创建计数数组int[] count = new int[max - min + 1];// 统计每个元素出现的次数for (int i = 0; i < arr.length; i++) {count[arr[i] - min]++;}// 更新计数数组，使其存储每个元素的实际位置for (int i = 1; i < count.length; i++) {count[i] += count[i - 1];}// 构建输出数组int[] output = new int[arr.length];for (int i = arr.length - 1; i >= 0; i--) {output[count[arr[i] - min] - 1] = arr[i];count[arr[i] - min]--;}// 将排序后的结果拷贝回原数组System.arraycopy(output, 0, arr, 0, arr.length);}// 打印数组public static void printArray(int[] arr) {for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}public static void main(String[] args) {int[] arr = {64, 25, 12, 22, 11};System.out.println("原始数组：");printArray(arr);countingSort(arr);System.out.println("排序后的数组：");printArray(arr);}
}

4）时间复杂度分析：

9、桶排序

1）基本思想：

桶排序是一种基于分布的排序算法，适用于数据均匀分布的场景。它的基本思想是：

将元素分到若干个桶中。
对每个桶中的元素进行排序（可以使用其他排序算法，如插入排序、快速排序等）。
合并所有桶中的元素，得到最终的排序结果。

桶排序通过将数据分布到不同的桶中，然后对每个桶内的数据进行排序，最后合并各个桶的数据。桶排序的效率很高，尤其适用于数据分布均匀的情况。

2）算法步骤：

创建桶：根据数据的范围和元素的数量创建若干个桶。
分配元素到桶：将数据中的每个元素根据其值分配到对应的桶中。
对每个桶内的元素进行排序：对每个桶中的元素使用其他排序算法（如插入排序）进行排序。
合并所有桶：将所有桶中的元素按顺序合并，得到排序后的结果。

3）代码实现（Java）：

import java.util.ArrayList;
import java.util.Collections;public class BucketSort {// 桶排序算法public static void bucketSort(float[] arr) {if (arr.length <= 1) return;// 创建桶，桶的数量等于数组的长度int n = arr.length;@SuppressWarnings("unchecked")ArrayList<Float>[] buckets = new ArrayList[n];// 初始化每个桶for (int i = 0; i < n; i++) {buckets[i] = new ArrayList<>();}// 将元素分配到桶中for (int i = 0; i < n; i++) {int index = (int) (arr[i] * n);  // 根据元素值决定桶的索引buckets[index].add(arr[i]);}// 对每个桶进行排序for (int i = 0; i < n; i++) {Collections.sort(buckets[i]);}// 将所有桶中的元素按顺序合并int index = 0;for (int i = 0; i < n; i++) {for (float num : buckets[i]) {arr[index++] = num;}}}// 打印数组public static void printArray(float[] arr) {for (float num : arr) {System.out.print(num + " ");}System.out.println();}public static void main(String[] args) {float[] arr = {0.42f, 0.32f, 0.53f, 0.37f, 0.21f, 0.44f, 0.85f};System.out.println("原始数组：");printArray(arr);bucketSort(arr);System.out.println("排序后的数组：");printArray(arr);}
}

4）时间复杂度分析：

10、基数排序

1）基本思想：

基数排序是一种非比较型排序算法，它通过将数据按位数逐步排序，先对最低有效位（LSD，Least Significant Digit）进行排序，然后依次排序到最高有效位（MSD，Most Significant Digit）。基数排序通常适用于整数和字符串的排序。

基数排序的基本思想是：

从最低有效位开始，按每个位的数字对数据进行排序。
对每一位的数字使用稳定的排序算法（如计数排序或桶排序）进行排序。
一直排序到最高有效位为止。

2）算法步骤：

确定数据的最大位数：找到数据中最大数的位数，这决定了排序的轮数。
按位数逐步排序：从最低有效位开始，对每一位使用稳定的排序算法（如计数排序）进行排序。
重复排序：按位数逐步排序直到最高有效位。

3）代码实现（Java）：

import java.util.Arrays;public class RadixSort {// 基数排序算法public static void radixSort(int[] arr) {// 找到数组中的最大值，以确定排序的轮数int max = Arrays.stream(arr).max().getAsInt();// 对每一位进行排序for (int exp = 1; max / exp > 0; exp *= 10) {countingSortByDigit(arr, exp);}}// 按照某一位（根据exp）的值进行计数排序private static void countingSortByDigit(int[] arr, int exp) {int n = arr.length;int[] output = new int[n];int[] count = new int[10];  // 基数是10，表示0到9// 统计每个数字在当前位的出现次数for (int i = 0; i < n; i++) {count[(arr[i] / exp) % 10]++;}// 计算每个元素最终位置的索引for (int i = 1; i < 10; i++) {count[i] += count[i - 1];}// 构建排序后的数组for (int i = n - 1; i >= 0; i--) {int digit = (arr[i] / exp) % 10;output[count[digit] - 1] = arr[i];count[digit]--;}// 将排序后的结果拷贝回原数组System.arraycopy(output, 0, arr, 0, n);}// 打印数组public static void printArray(int[] arr) {for (int num : arr) {System.out.print(num + " ");}System.out.println();}public static void main(String[] args) {int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};System.out.println("原始数组：");printArray(arr);radixSort(arr);System.out.println("排序后的数组：");printArray(arr);}
}