冒泡排序算法与选择排序算法（最主流常见的排序算法有哪些）
本文给大家介绍10种排序算法：冒泡排序 (Bubble Sort)、选择排序 (Selection Sort)、插入排序 (Insertion Sort)、希尔排序 (Shell Sort)、归并排序 (Merge sort)、快速排序 (Quick Sort)、堆排序 (Heap Sort)、计数排序 (Counting Sort)、桶排序 (Bucket Sort)、基数排序 (Radix Sort) ，接下来我们就来聊聊关于冒泡排序算法与选择排序算法?以下内容大家不妨参考一二希望能帮到您!
冒泡排序算法与选择排序算法
本文给大家介绍10种排序算法：冒泡排序 (Bubble Sort)、选择排序 (Selection Sort)、插入排序 (Insertion Sort)、希尔排序 (Shell Sort)、归并排序 (Merge sort)、快速排序 (Quick Sort)、堆排序 (Heap Sort)、计数排序 (Counting Sort)、桶排序 (Bucket Sort)、基数排序 (Radix Sort)
一、冒泡排序 (Bubble Sort)
冒泡排序它的工作原理是通过比较相邻的元素来排序，每次都尽量让最大（或最小）的元素“浮”到最顶端（或最底端）
冒泡排序算法的流程如下：
- 从第一个元素开始，依次比较相邻的两个元素，如果它们的顺序不对，就交换它们的位置。
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
以下是冒泡排序的java实现：
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
int[] array = {3, 6, 2, 1,34, 9,23, 4, 5, 8, 7};
bubbleSort(array);
System.out.println(Arrays.toString(array));
//输出结果 [1, 2, 3, 4, 5, 6, 7, 8, 9, 23, 34]
}
/**
* 冒泡排序
* @param array
*/
public static void bubbleSort(int[] array) {
for (int i = 0; i < array.length; i ) {
for (int j = 0; j < array.length - i - 1; j ) {
if (array[j] > array[j 1]) {
int temp = array[j];
array[j] = array[j 1];
array[j 1] = temp;
}
}
}
}
}
冒泡排序的时间复杂度是 O(n^2)，空间复杂度是 O(1)。它是一种稳定的排序算法，冒泡排序是一种时间复杂度较高的排序算法，它不适用于大型数据集，但它的实现非常简单，对于小型数据集来说是一种很好的选择。
二、选择排序 (Selection Sort)
选择排序它的工作原理是通过枚举序列中的每个数，找到最小（或最大）的数，并将其与序列的第一个数进行交换。然后，再从剩下的数中找到最小（或最大）的数，并将其与序列的第二个数进行交换，依此类推，直到将整个序列排好序。
选择排序算法的流程如下：
- 从第一个元素开始，找到整个序列中最小的数。
- 将最小的数和第一个元素交换位置。
- 从第二个元素开始，找到剩余序列中最小的数。
- 将最小的数和第二个元素交换位置。
- 以此类推，直到将整个序列排好序。
import java.util.Arrays;
public class SelectionSort {
public static void main(String[] args) {
int[] array = {3, 6, 2, 34, 37, 1, 9, 4, 5, 8, 7};
selectionSort(array);
System.out.println(Arrays.toString(array));
//输出结果 [1, 2, 3, 4, 5, 6, 7, 8, 9, 34, 37]
}
public static void selectionSort(int[] array) {
for (int i = 0; i < array.length; i ) {
int minIndex = i;
for (int j = i 1; j < array.length; j ) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
int temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
}
}
选择排序的时间复杂度是 O(n^2)，空间复杂度是 O(1)。它是一种不稳定的排序算法，选择排序的优点是实现简单，在小型数据集上表现较好，但它的时间复杂度较高，不适用于大型数据集。
三、插入排序 (Insertion Sort)
插入排序它的工作原理是通过构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序算法的流程如下：
- 从第一个元素开始，该元素可以认为已经被排序。
- 取出下一个元素，在已经排序的元素序列中从后向前扫描。
- 如果该元素（已排序）大于新元素，将该元素移到下一位置。
- 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置。
- 将新元素插入到该位置后。
- 重复步骤 2~5。
import java.util.Arrays;
public class InsertionSort {
public static void main(String[] args) {
int[] array = {3, 6, 2, 34, 56, 1, 9, 4, 5, 8, 7};
insertionSort(array);
System.out.println(Arrays.toString(array));
//输出结果 [1, 2, 3, 4, 5, 6, 7, 8, 9]
}
public static void insertionSort(int[] array) {
for (int i = 1; i < array.length; i ) {
int value = array[i];
int j = i - 1;
while (j >= 0 && array[j] > value) {
array[j 1] = array[j];
j--;
}
array[j 1] = value;
}
}
}
插入排序的时间复杂度是 O(n^2)，空间复杂度是 O(1)。它是一种稳定的排序算法，插入排序的优点是实现简单，在小型数据集上表现较好。对于比较有序的数据，插入排序的时间复杂度可以达到 O(n) 级别，它的优势在于，对于基本有序的数据，插入排序的效率是比较高的。因此，插入排序常常被用作其他排序算法的辅助排序算法，比如希尔排序，但是，由于插入排序的时间复杂度仍然是 O(n^2) 级别，所以它不适用于大型数据集。
四、希尔排序 (Shell Sort)
希尔排序他的原理是使用不同的间隔将序列分组，然后对每组进行插入排序。这种方法可以在保留插入排序优点的同时，提高排序效率。
以下是希尔排序的Java实现：
import java.util.Arrays;
public class ShellSort {
public static void main(String[] args) {
int[] array = {3, 6, 2, 34, 56, 1, 9, 4, 5, 8, 7};
ShellSort.sort(array);
System.out.println(Arrays.toString(array));
//输出结果 [1, 2, 3, 4, 5, 6, 7, 8, 9, 34, 56]
}
public static void sort(int[] arr) {
int n = arr.length;
// 计算 Knuth 序列
int h = 1;
while (h < n / 3) {
h = 3 * h 1;
}
while (h >= 1) {
// 从第 h 个元素，逐个对其所在组进行直接插入排序操作
for (int i = h; i < n; i ) {
int j = i;
int temp = arr[i];
while (j - h >= 0 && temp < arr[j - h]) {
arr[j] = arr[j - h];
j -= h;
}
arr[j] = temp;
}
h /= 3;
}
}
}
首先，我们需要生成 Knuth 序列。在这个序列中，h[i 1] = 3*h[i] 1。
int h = 1;
while (h < n / 3) {
h = 3 * h 1;
}
然后，我们开始遍历 Knuth 序列。每一次遍历，我们都会使数组变为 h 有序。
在每一次遍历中，我们从第 h 个元素开始，逐个对其所在组进行直接插入排序操作。直接插入排序是一种简单的排序算法，它的原理是将待排序元素与已排序序列逐一比较，如果比已排序元素小，则交换位置。
while (h >= 1) {
// 从第 h 个元素，逐个对其所在组进行直接插入排序操作
for (int i = h; i < n; i ) {
int j = i;
int temp = arr[i];
while (j - h >= 0 && temp < arr[j - h]) {
arr[j] = arr[j - h];
j -= h;
}
arr[j] = temp;
}
h /= 3;
}
最后，我们将 h 除以 3，继续遍历下一个 h 值。当 h=1 时，数组就是有序的。
希尔排序是一种插入排序算法，它的优点是比较适用于大规模的数据集，且对于大多数数据集来说，其效率要高于直接插入排序，希尔排序的时间复杂度取决于使用的 h 序列。如果使用单调不降序列，例如 Knuth 序列，算法的时间复杂度为 O(n^1.5)，在实际使用中，希尔排序的效率并不一定会比其他排序算法更优。因此，建议在实际项目中，先使用其他算法，如快速排序、归并排序，再尝试希尔排序，希尔排序并不常用，但是它对于理解插入排序算法的原理有很大的帮助。
五、归并排序 (Merge Sort)
归并排序它的基本思想是将待排序序列不断分成较小的子序列，然后对子序列进行排序，最后将排好序的子序列合并成一个有序的序列。
以下是归并排序的Java实现：
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) {
int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};
MergeSort.sort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
//输出结果 [1, 2, 3, 4, 5, 6, 7, 8, 9]
}
public static void sort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left right) / 2;
sort(arr, left, mid);
sort(arr, mid 1, right);
merge(arr, left, mid, right);
}
}
private static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left 1;
int n2 = right - mid;
int[] L = new int[n1];
int[] R = new int[n2];
for (int i = 0; i < n1; i ) {
L[i] = arr[left i];
}
for (int j = 0; j < n2; j ) {
R[j] = arr[mid 1 j];
}
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i ;
} else {
arr[k] = R[j];
j ;
}
k ;
}
while (i < n1) {
arr[k] = L[i];
i ;
k ;
}
while (j < n2) {
arr[k] = R[j];
j ;
k ;
}
}
}
在 上面代码中，我们使用了递归的方式来实现归并排序。首先，我们将数组递归地分成两半，直到每个子序列只包含一个元素为止。然后，我们开始合并子序列，使用两个指针来遍历两个子序列，比较两个指针指向的元素，将较小的元素放到新的数组中，然后将指针向后移，直到两个子序列都遍历完为止。最后，我们将新的数组复制到原数组中。
归并排序的时间复杂度为 O(nlogn)，空间复杂度为 O(n)。它是一种稳定的排序算法。
六、快速排序 (Quick Sort)
快速排序它的基本思想是通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
以下是快速排序的Java实现：
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};
QuickSort.sort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
//输出结果 [1, 2, 3, 4, 5, 6, 7, 8, 9]
}
public static void sort(int[] arr, int left, int right) {
if (left < right) {
int pivotIndex = partition(arr, left, right);
sort(arr, left, pivotIndex - 1);
sort(arr, pivotIndex 1, right);
}
}
private static int partition(int[] arr, int left, int right) {
int pivot = arr[right];
int i = left - 1;
for (int j = left; j < right; j ) {
if (arr[j] < pivot) {
i ;
swap(arr, i, j);
}
}
swap(arr, i 1, right);
return i 1;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
在上面的代码中，partition 函数的作用是找到一个枢纽元并将数组划分为两部分。我们使用一个指针 i 来遍历数组，如果当前元素小于枢纽元，就将它与 i 交换位置。最后，我们将枢纽元放到 i 的后面，返回 i。
快速排序是一种非常常用的排序算法，在很多场景下都可以使用。例如：
- 排序大量数据。快速排序的时间复杂度为 O(nlogn)，因此在排序大量数据时效率较高。
- 排序时间复杂度要求较高的场景。对于一些时间复杂度要求较高的应用，快速排序可能是一个不错的选择。
- 排序时间复杂度和空间复杂度要求平衡的场景。快速排序既保证了时间复杂度，又有较小的空间复杂度，因此在时间复杂度和空间复杂度要求平衡的场景下也可以使用。
当然，快速排序也有一些缺点：
- 不稳定。快速排序是一种不稳定的排序算法，它可能会打乱相同元素的相对顺序。
- 枢纽元选择不当时可能导致时间复杂度退化。如果枢纽元选择不当，例如总是选择数组的第一个元素作为枢纽元，则快速排序的时间复杂度可能退化到 O(n^2)
- 快速排序的时间复杂度是受数据的初始顺序影响的。如果数据已经有序，则快速排序的时间复杂度会退化到 O(n^2)。
七、堆排序 (Heap Sort)
堆排序它的基本思想是通过构建大根堆或者小根堆，然后不断地将堆顶元素与末尾元素交换位置，最终达到排序的目的，堆排序的流程如下：
- 构建大根堆。
- 将堆顶元素与末尾元素交换位置。
- 重新维护堆的性质。
- 重复步骤 2 和 3，直到堆为空。
以下是堆排序的 Java 代码：
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) {
int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};
HeapSort.sort(arr);
System.out.println(Arrays.toString(arr));
//输出结果 [1, 2, 3, 4, 5, 6, 7, 8, 9]
}
public static void sort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left right) / 2;
sort(arr, left, mid);
sort(arr, mid 1, right);
merge(arr, left, mid, right);
}
}
private static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left 1;
int n2 = right - mid;
int[] L = new int[n1];
int[] R = new int[n2];
for (int i = 0; i < n1; i ) {
L[i] = arr[left i];
}
for (int j = 0; j < n2; j ) {
R[j] = arr[mid 1 j];
}
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i ;
} else {
arr[k] = R[j];
j ;
}
k ;
}
while (i < n1) {
arr[k] = L[i];
i ;
k ;
}
while (j < n2) {
arr[k] = R[j];
j ;
k ;
}
}
}
在上面堆排序的 Java 代码中，我们定义了一个 sort 函数用于对数组进行排序。
首先，我们使用一个循环构建大根堆。在构建过程中，我们使用 heapify 函数来维护堆的性质，然后，我们使用另一个循环不断地将堆顶元素与末尾元素交换位置，直到堆为空，heapify 函数的作用是维护堆的性质。它首先找到当前节点 i 和它的左右儿子中最大的元素，如果最大的元素不是当前节点 i，就将它们交换位置。然后递归调用 heapify 函数，继续维护堆的性质swap 函数的作用是交换数组中两个元素的位置。
堆排序的时间复杂度为 O(nlogn)，空间复杂度为 O(1)。它是一种不稳定的排序算法。
八、计数排序 (Counting Sort)
计数排序它的基本思想是统计数组中每个值出现的次数，然后根据这个次数来排序。计数排序适用于数据范围不大的场景，因为它的时间复杂度和数据范围呈线性关系。
以下是计数排序的 Java 代码：
import java.util.Arrays;
public class CountingSort {
public static void main(String[] args) {
int[] array = {3, 6, 2, 34, 56, 1, 9, 4, 5, 8, 7};
CountingSort.sort(array);
System.out.println(Arrays.toString(array));
// 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9, 34, 56]
}
public static void sort(int[] arr) {
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 range = max - min 1;
int[] count = new int[range];
for (int i = 0; i < arr.length; i ) {
count[arr[i] - min] ;
}
int k = 0;
for (int i = 0; i < range; i ) {
while (count[i]-- > 0) {
arr[k ] = i min;
}
}
}
}
在计数排序的 Java 代码中，我们首先遍历数组，找到数组中的最大值和最小值。然后我们创建一个 count 数组，用于统计每个值出现的次数。接着，我们再次遍历数组，根据 count 数组来排序结果，计数排序的优点在于它的时间复杂度很低，只和数据范围有关。但是，计数排序的缺点在于它只适用于数据范围不大的场景，因为它需要开辟一个大小为数据范围的数组来存储计数信息。如果数据范围很大，则空间复杂度就会变得很高，不适用于实际应用。
计数排序的时间复杂度为 O(n k)，其中 k 是数据范围。空间复杂度为 O(k)。它是一种稳定的排序算法
九、桶排序 (Bucket Sort)
桶排序是一种排序算法，它的基本思想是将数据分到有限数量的桶子里，然后对每个桶内的数据分别进行排序。桶排序适用于数据范围很大，但是数据分布在一个较小范围内的场景
以下是桶排序的 Java 代码：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class BucketSort {
public static void main(String[] args) {
int[] array = {3, 6, 2, 34, 56, 1, 9, 4, 5, 8, 7};
CountingSort.sort(array);
System.out.println(Arrays.toString(array));
// 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9, 34, 56]
}
public static void sort(int[] arr) {
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 bucketCount = (max - min) / arr.length 1;
List<List<Integer>> buckets = new ArrayList<>(bucketCount);
for (int i = 0; i < bucketCount; i ) {
buckets.add(new ArrayList<>());
}
for (int i = 0; i < arr.length; i ) {
buckets.get((arr[i] - min) / arr.length).add(arr[i]);
}
int k = 0;
for (List<Integer> bucket : buckets) {
Collections.sort(bucket);
for (int i : bucket) {
arr[k ] = i;
}
}
}
}
在桶排序的上面代码中，我们计算出需要的桶数量，然后创建一个桶的列表，接着，我们遍历数组，将每个数据放入对应的桶中，最后，我们遍历桶的列表，对每个桶内的数据分别进行排序，然后将排序后的数据放回原数组中，桶排序的优点在于它可以快速地对数据进行排序，特别是对于数据范围很大，但是数据分布在一个较小范围内的情况。但是，桶排序的缺点在于它需要额外的空间来存储桶。如果数据范围很大，则需要开辟大量的空间来存储桶，这可能会导致空间问题。
此外，桶排序还需要对桶内的数据进行排序，而这个排序的时间复杂度取决于桶内的数据的数量，如果桶内的数据数量很大，则排序的时间复杂度也会变得很高。因此，桶排序并不是一种适用于所有场景的排序算法。
桶排序的时间复杂度为 O(n k)，其中 k 是桶的数量。空间复杂度为 O(n k)。桶排序是一种稳定的排序算法。
十、基数排序 (Radix Sort)
基数排序是一种排序算法，它的基本思想是将数据的每一位进行排序，从低位到高位逐次排序。基数排序适用于数据范围很大，但是数据分布在一个较小范围内的场景。
以下是基数排序的 Java 代码：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class BucketSort {
public static void main(String[] args) {
int[] array = {3, 6, 2, 34, 56, 1, 9, 4, 5, 8, 7};
CountingSort.sort(array);
System.out.println(Arrays.toString(array));
// 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9, 34, 56]
}
public static void sort(int[] arr) {
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 bucketCount = (max - min) / arr.length 1;
List<List<Integer>> buckets = new ArrayList<>(bucketCount);
for (int i = 0; i < bucketCount; i ) {
buckets.add(new ArrayList<>());
}
for (int i = 0; i < arr.length; i ) {
buckets.get((arr[i] - min) / arr.length).add(arr[i]);
}
int k = 0;
for (List<Integer> bucket : buckets) {
Collections.sort(bucket);
for (int i : bucket) {
arr[k ] = i;
}
}
}
}
基数排序的时间复杂度为 O(n*k)，其中 k 是数据的位数。空间复杂度为 O(n k)。
在基数排序的 Java 代码中，我们遍历数组，将每个数据放入对应的桶中。具体的，我们使用数据的某一位来决定将数据放入哪个桶中，最后，我们遍历桶的列表，将桶内的数据放回原数组中，然后清空桶，基数排序的优点在于它可以快速地对数据进行排序，特别是对于数据范围很大，但是数据分布在一个较小范围内的情况。但是，基数排序的缺点在于它需要额外的空间来存储桶。如果数据范围很大，则需要开辟大量的空间来存储桶，这可能会导致空间问题，此外，基数排序还需要遍历数据多次，具体的，需要遍历数据的位数次，如果数据的位数很多，则基数排序的时间复杂度也会变得很高。因此，基数排序并不是一种适用于所有场景的排序算法。
最后总结一下算法的优劣势，供大家参考，好了，写完了，大家可以发表自己的看法以及想法共同探讨！
写作不易，希望大家动动手指点赞关注收藏，谢谢！
|
排序算法 |
优点 |
缺点 |
|
冒泡排序 |
简单易实现 |
时间复杂度高，不适合大规模数据 |
|
选择排序 |
简单易实现 |
时间复杂度高，不适合大规模数据 |
|
插入排序 |
时间复杂度低，适合小规模数据 |
不适合大规模数据 |
|
希尔排序 |
时间复杂度低，适合大规模数据 |
不稳定 |
|
归并排序 |
时间复杂度低，稳定 |
需要额外空间 |
|
快速排序 |
时间复杂度低，不需要额外空间 |
不稳定 |
|
堆排序 |
时间复杂度低，不需要额外空间 |
不稳定 |
|
计数排序 |
时间复杂度低，适合数据范围较小的情况 |
需要额外空间 |
|
桶排序 |
时间复杂度低，适合数据范围较小的情况 |
需要额外空间 |
|
基数排序 |
时间复杂度低，适合数据范围较大，但数据分布在较小范围内的情况 |
需要额外空间，时间复杂度随着数据位数的增加而增 |
,
免责声明：本文仅代表文章作者的个人观点，与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺，请读者仅作参考，并自行核实相关内容。文章投诉邮箱：anhduc.ph@yahoo.com
