1. 冒泡排序
最简单的一种排序算法。假设长度为n的数组arr，要按照从小到大排序。则冒泡排序的具体过程可以描述为：首先从数组的第一个元素开始到数组最后一个元素为止，对数组中相邻的两个元素进行比较，如果位于数组左端的元素大于数组右端的元素，则交换这两个元素在数组中的位置。这样操作后数组最右端的元素即为该数组中所有元素的最大值。接着对该数组除最右端的n-1个元素进行同样的操作，再接着对剩下的n-2个元素做同样的操作，直到整个数组有序排列。算法的时间复杂度为O(n^2)。
public static void bubbleSort(int[] arr, int len) {
for(int i = 0; i < len; i++) {
for(int j = 0; j < len - i - 1; j++) {
// 左边到右边是从小到大的排序
if(arr[j] > arr[j + 1]) {
int temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
}
return;
}
}
2. 选择排序
每一趟在n-i+1(i=1,2,…,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。具体来说，假设长度为n的数组arr，要按照从小到大排序
- 那么先从n个数字中找到最小值min1，如果最小值min1的位置不在数组的最左端(也就是min1不等于arr[0])，则将最小值min1和arr[0]交换，
- 接着在剩下的n-1个数字中找到最小值min2，如果最小值min2不等于arr[1]，则交换这两个数字，
- 依次类推，直到数组arr有序排列。算法的时间复杂度为O(n^2)。
public static void selectionSort(int[] arr, int len) {
int index , temp;
for(int i = 0; i < len; i++) {
index = i;
for(int j = i + 1; j < len; j++) {
if(arr[j] < arr[index]) {
index = j;
}
}
if(index != i) {
temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
}
}
return;
}
3. 插入排序
插入排序的基本思想就是将无序序列插入到有序序列中。
插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。
将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
public static void insertSort(int[] arr, int len) {
// 从下标为1的元素开始选择合适的位置插入，因为下标为0只有一个元素，默认是有序的
for(int i = 1; i < arr.length; i++) {
//记录要插入的数据
int temp = arr[i];
// 从已经排序的序列最右边开始比较，找到比他小的数
//序列最右边是j-1，就每次比较要插入的数arr[i]和arr[j-1]
int j = i;
while (j > 0 && temp < arr[j - 1]) {
// 如果arr[j-1] > temp
arr[j] = arr[j - 1]; // 就把arr[j-1]的位置移到arr[j]
j--;
}
// 存在比其它小的数，插入
if(j != i) {
arr[j] = temp;
}
}
return;
}
4. 希尔排序
希尔排序(Shell’s Sort)在插入排序算法的基础上进行了改进，算法的时间复杂度与前面几种算法相比有较大的改进。其算法的基本思想是：
把待排序的数列按照一定的增量分割成多个子数列。但是这个子数列不是连续的，而是通过前面提到的增量，按照一定相隔的增量进行分割的，然后对各个子数列进行插入排序，接着增量逐渐减小，然后仍然对每部分进行插入排序，在减小到1之后直接使用插入排序处理数列。
// 插入排序
void ShellSort(int arr[], int length)
{
int increasement = length;
int i, j, k;
do
{
// 确定分组的增量
increasement = increasement / 3 + 1;
for (i = 0; i < increasement; i++)
{
for (j = i + increasement; j < length; j += increasement)
{
if (arr[j] < arr[j - increasement])
{
int temp = arr[j];
for (k = j - increasement; k >= 0 && temp < arr[k]; k -= increasement)
{
arr[k + increasement] = arr[k];
}
arr[k + increasement] = temp;
}
}
}
} while (increasement > 1);
}
5. 快速排序
在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n^2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
快速排序的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，已达到整个序列有序。一趟快速排序的具体过程可描述为：从待排序列中任意选取一个记录(通常选取第一个记录)作为基准值，然后将记录中关键字比它小的记录都安置在它的位置之前，将记录中关键字比它大的记录都安置在它的位置之后。这样，以该基准值为分界线，将待排序列分成的两个子序列。
一趟快速排序的具体做法为：设置两个指针low和high分别指向待排序列的开始和结尾，记录下基准值baseval(待排序列的第一个记录)，然后先从high所指的位置向前搜索直到找到一个小于baseval的记录并互相交换，接着从low所指向的位置向后搜索直到找到一个大于baseval的记录并互相交换，重复这两个步骤直到low=high为止。
// 快速排序
void QuickSort(int arr[], int start, int end)
{
if (start >= end)
return;
int i = start;
int j = end;
// 基准数
int baseval = arr[start];
while (i < j)
{
// 从右向左找比基准数小的数
while (i < j && arr[j] >= baseval)
{
j--;
}
if (i < j)
{
arr[i] = arr[j];
i++;
}
// 从左向右找比基准数大的数
while (i < j && arr[i] < baseval)
{
i++;
}
if (i < j)
{
arr[j] = arr[i];
j--;
}
}
// 把基准数放到i的位置
arr[i] = baseval;
// 递归
QuickSort(arr, start, i - 1);
QuickSort(arr, i + 1, end);
}
6. 归并排序
“归并”的含义是将两个或两个以上的有序序列组合成一个新的有序表。假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n/2]（[x]表示不小于x的最小整数）个长度为2(或者是1)的有序子序列，再两两归并。如此重复，直到得到一个长度为n的有序序列为止。这种排序方法称为2-路归并排序。
// 归并排序
void MergeSort(int arr[], int start, int end, int * temp)
{
if (start >= end)
return;
int mid = (start + end) / 2;
MergeSort(arr, start, mid, temp);
MergeSort(arr, mid + 1, end, temp);
// 合并两个有序序列
int length = 0; // 表示辅助空间有多少个元素
int i_start = start;
int i_end = mid;
int j_start = mid + 1;
int j_end = end;
while (i_start <= i_end && j_start <= j_end)
{
if (arr[i_start] < arr[j_start])
{
temp[length] = arr[i_start];
length++;
i_start++;
}
else
{
temp[length] = arr[j_start];
length++;
j_start++;
}
}
while (i_start <= i_end)
{
temp[length] = arr[i_start];
i_start++;
length++;
}
while (j_start <= j_end)
{
temp[length] = arr[j_start];
length++;
j_start++;
}
// 把辅助空间的数据放到原空间
for (int i = 0; i < length; i++)
{
arr[start + i] = temp[i];
}
}
7. 堆排序
可以将堆看做是一个完全二叉树。并且，每个结点的值都大于等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于等于其左右孩子结点的值，称为小顶堆。
堆排序(Heap Sort)是利用堆进行排序的方法。其基本思想为：将待排序列构造成一个大顶堆(或小顶堆)，整个序列的最大值(或最小值)就是堆顶的根结点，将根节点的值和堆数组的末尾元素交换，此时末尾元素就是最大值(或最小值)，然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次大值(或次小值)，如此反复执行，最终得到一个有序序列。
/*
@param arr 待调整的数组
@param i 待调整的结点的下标
@param length 数组的长度
*/
void HeapAdjust(int arr[], int i, int length)
{
// 调整i位置的结点
// 先保存当前结点的下标
int max = i;
// 当前结点左右孩子结点的下标
int lchild = i * 2 + 1;
int rchild = i * 2 + 2;
if (lchild < length && arr[lchild] > arr[max])
{
max = lchild;
}
if (rchild < length && arr[rchild] > arr[max])
{
max = rchild;
}
// 若i处的值比其左右孩子结点的值小，就将其和最大值进行交换
if (max != i)
{
int temp;
temp = arr[i];
arr[i] = arr[max];
arr[max] = temp;
// 递归
HeapAdjust(arr, max, length);
}
}
// 堆排序
void HeapSort(int arr[], int length)
{
// 初始化堆
// length / 2 - 1是二叉树中最后一个非叶子结点的序号
for (int i = length / 2 - 1; i >= 0; i--)
{
HeapAdjust(arr, i, length);
}
// 交换堆顶元素和最后一个元素
for (int i = length - 1; i >= 0; i--)
{
int temp;
temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
HeapAdjust(arr, 0, i);
}
}
8. 计数排序
计数排序最核心的思想就是计数序列中每个元素出现的次数
- 第一次遍历序列,找出序列中的最大值以及最小值,然后根据最大值MAX与最小值MIN创建一个MAX-MIN+1长度的数组.为什么创建这样长度的数组呢,因为只有创建了这样长度的数组,MIN-MAX区间内的每个元素才有对应的位置进行存放
2. .第二次遍历序列,我们每次遍历一个元素都将该元素所对应的区间数组对应的位置进行+1操作,这个步骤其实就是我们计数排序的核心----计数了.遍历结束之后,区间数组中的元素值就代表相应元素出现的次数,如下图所示: - 最后一步就只需要按照区间数组中的次数一次将该元素打印出来即可
public class CountingSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝，不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
int maxValue = getMaxValue(arr);
return countingSort(arr, maxValue);
}
private int[] countingSort(int[] arr, int maxValue) {
int bucketLen = maxValue + 1;
int[] bucket = new int[bucketLen];
for (int value : arr) {
bucket[value]++;
}
int sortedIndex = 0;
for (int j = 0; j < bucketLen; j++) {
while (bucket[j] > 0) {
arr[sortedIndex++] = j;
bucket[j]--;
}
}
return arr;
}
private int getMaxValue(int[] arr) {
int maxValue = arr[0];
for (int value : arr) {
if (maxValue < value) {
maxValue = value;
}
}
return maxValue;
}
}
9. 桶排序
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：
- 在额外空间充足的情况下，尽量增大桶的数量
- 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
对于桶中元素的排序，选择何种比较排序算法
- 什么时候最快：当输入的数据可以均匀的分配到每一个桶中。
- 什么时候最慢：当输入的数据被分配到了同一个桶中。
- 示意图
-
元素分布在桶中：
![[图片]](https://img-blog.csdnimg.cn/4a1dad11f26342968b056cbff3f1721d.png)
-
元素在每个桶中排序
![[图片]](https://img-blog.csdnimg.cn/48e483facf6544c4af45abf0656f14c9.png)
-
private static final InsertSort insertSort = new InsertSort();
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝，不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
return bucketSort(arr, 5);
}
private int[] bucketSort(int[] arr, int bucketSize) throws Exception {
if (arr.length == 0) {
return arr;
}
int minValue = arr[0];
int maxValue = arr[0];
for (int value : arr) {
if (value < minValue) {
minValue = value;
} else if (value > maxValue) {
maxValue = value;
}
}
int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
int[][] buckets = new int[bucketCount][0];
// 利用映射函数将数据分配到各个桶中
for (int i = 0; i < arr.length; i++) {
int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
buckets[index] = arrAppend(buckets[index], arr[i]);
}
int arrIndex = 0;
for (int[] bucket : buckets) {
if (bucket.length <= 0) {
continue;
}
// 对每个桶进行排序，这里使用了插入排序
bucket = insertSort.sort(bucket);
for (int value : bucket) {
arr[arrIndex++] = value;
}
}
return arr;
}
/**
* 自动扩容，并保存数据
*
* @param arr
* @param value
*/
private int[] arrAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
return arr;
}
}