(1) 算法过程
- 比较相邻的元素。如果第一个比第二个大（升序），就交换它们两个；
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对，最后的元素应该会是最大的数；
- 针对所有的元素重复以上的步骤，除了最后一个；
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
- 特点：
1、 需要循环array.length-1次 外层循环
2、 每次排序的次数逐步递减
3、 也可能存在本次排序没有发生变化
(2) 代码实现
以下是冒泡排序的一个Java实现：
public class BubbleSort { 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]) { // swap arr[j+1] and arr[j] int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } }
3.3 快速排序 (Quick Sort)
快速排序是一种高效的排序算法，是对冒泡排序的一种改进，使用了分治的思想。算法选择一个元素作为“基准”，将要排序的数据分割成两部分，一部分的所有数据都比另一部分的所有数据要小。然后再按此方法对这两部分数据分别进行快速排序。它是一种被广泛使用的排序算法，性能良好的实现的期望时间复杂度为O(n log n)。
(1) 算法过程
从数列中挑出一个元素，称为"基准"（pivot）;
重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列进行排序。
(2) 代码实现
以下是快速排序的一个Java实现：
class QuickSort { int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = (low-1); // index of smaller element for (int j=low; j<high; j++) { if (arr[j] < pivot) { i++; // swap arr[i] and arr[j] int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } // swap arr[i+1] and arr[high] (or pivot) int temp = arr[i+1]; arr[i+1] = arr[high]; arr[high] = temp; return i+1; } void sort(int arr[], int low, int high) { if (low < high) { int pi = partition(arr, low, high); sort(arr, low, pi-1); sort(arr, pi+1, high); } } }
总结一下，冒泡排序和快速排序都是比较型排序，但冒泡排序是稳定排序，而快速排序是不稳定的排序。对于冒泡排序，时间复杂度为O(n²)，空间复杂度为O(1)；而快速排序，最好情况下时间复杂度为O(n log n)，最坏情况为O(n²)，平均情况为O(n log n)，空间复杂度为O(log n)。
3.4 插入排序 (Insertion Sort)
插入排序是一种简单的排序算法，它模仿了人们整理扑克牌的方式。它的工作原理是通过构造一个有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序，即只需用到O(1)的额外空间的排序，最坏时间复杂度为O(n^2)，使得插入排序适用于数据量小的排序。
(1) 算法过程
从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤2~5。
(2) 代码实现
以下是插入排序的一个Java实现：
public class InsertionSort { 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; } } }
3.5 选择排序 (Selection Sort)
选择排序是一种简单直观的排序算法，无论什么数据进去都是O(n²)的时间复杂度。所以用到它的时候，数据规模越小越好。
(1) 算法过程
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；
- 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
- 重复第二步，直到所有元素均排序完毕。
(2) 代码实现
以下是选择排序的一个Java实现：
public class SelectionSort { void selectionSort(int arr[]) { int n = arr.length; for (int i = 0; i < n-1; i++) { // Find the minimum element in unsorted array int min_idx = i; for (int j = i+1; j < n; j++) if (arr[j] < arr[min_idx]) min_idx = j; // Swap the found minimum element with the first element int temp = arr[min_idx]; arr[min_idx] = arr[i]; arr[i] = temp; } } }
总结一下，插入排序和选择排序也是比较型排序，且它们都是稳定的排序方法。对于插入排序，时间复杂度为O(n²)，空间复杂度为O(1)；而选择排序，时间复杂度为O(n²)，空间复杂度为O(1)。尽管在最坏情况下，这两种算法都需要进行O(n²)次比较，但是插入排序在输入数据接近或已经排序的情况下，表现更优。
3.6 希尔排序 (Shell Sort)
希尔排序，也称递减增量排序，是插入排序的一种更高效的改进版本。
(1) 算法过程
希尔排序的基本思想是将数组列在一个表中并对列分别进行插入排序，重复这过程，不过每次使用一短的间隔（称为增量），然后将开始时用的最大增量减小（例如减半）。当增量减至1时，整个文件恰被分成一列，算法便终止。
(2) 代码实现
以下是希尔排序的一个Java实现：
public class ShellSort { void shellSort(int arr[]) { int n = arr.length; for (int gap = n / 2; gap > 0; gap /= 2) { for (int i = gap; i < n; i += 1) { int temp = arr[i]; int j; for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) arr[j] = arr[j - gap]; arr[j] = temp; } } } }
3.7 归并排序 (Merge Sort)
归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，适用于大规模数据。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
(1) 算法过程
归并排序采用分治法（Divide and Conquer）的思想。首先将大问题分解为小问题（将待排序序列分解为尽可能相等的两部分），然后对各个小问题进行解决（对每部分分别进行排序），最后将解决小问题的答案合并起来解决原来的大问题（将两个有序的子序列合并成一个有序序列）。
我们需要将两个已经有序的子序列合并成一个有序序列，比如上图最后一次合并，将[2,4,5,6]和[1,3,7,8]已经有序的子序列合并最终序列[1,2,3,4,5,6,7,8]
(2) 代码实现
以下是归并排序的一个Java实现：
public class MergeSort { void merge(int arr[], int left, int middle, int right) { int n1 = middle - left + 1; int n2 = right - middle; int leftArray[] = new int [n1]; int rightArray[] = new int [n2]; for (int i=0; i<n1; ++i) leftArray[i] = arr[left + i]; for (int j=0; j<n2; ++j) rightArray[j] = arr[middle + 1+ j]; int i = 0, j = 0; int k = left; while (i < n1 && j < n2) { if (leftArray[i] <= rightArray[j]) { arr[k] = leftArray[i]; i++; } else { arr[k] = rightArray[j]; j++; } k++; } while (i < n1) { arr[k] = leftArray[i]; i++; k++; } while (j < n2) { arr[k] = rightArray[j]; j++; k++; } } void sort(int arr[], int left, int right) { if (left < right) { int middle = (left+right)/2; sort(arr, left, middle); sort(arr , middle+1, right); merge(arr, left, middle, right); } } }
希尔排序和归并排序都是有效的排序算法。希尔排序是一种插入排序的改进版本，其时间复杂度为O(n log n)；而归并排序使用了分治策略，其时间复杂度为O(n log n)，但需要O(n)的额外空间。在对效率要求较高的场景中，这两种排序方法都是不错的选择。
4. 结语
本文主要详细介绍了常见的7种排序算法：基数排序、冒泡排序、快速排序、插入排序、选择排序、希尔排序和归并排序。我们针对每一种算法都给出了算法过程的详细说明，以及对应的Java实现。每种排序算法都有其特定的应用场景，了解和掌握这些算法，可以帮助我们更好地解决实际问题。
值得注意的是，排序算法的效率会受到数据规模和数据分布的影响。因此，选择排序算法时，除了考虑其时间和空间复杂度外，还需要根据实际情况选择最适合的算法。例如，对于小规模或者部分有序的数据，插入排序可能是一个不错的选择。而对于大规模的数据，我们可能需要选择时间复杂度较低的排序算法，如快速排序、归并排序等。
这些排序算法在计算机科学和软件工程领域都有着广泛的应用，是每一个程序员必备的基础知识。希望本文的内容对你有所帮助，如果有任何问题或者建议，欢迎留言讨论。
