一、选择排序算法描述
- 初始状态：无序区为R[1..n]，有序区为空；
- 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选 出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
- n-1趟结束，数组有序化了。
/**
* 选择排序算法：最好、平均、最坏时间复杂度均为O(n²)，空间复杂度为1，稳定性：不稳
*/
static void selectSort(int[] arr) {
for (int j = 0; j < arr.length - 1; j++) {
int minPos = j;
for (int i = j + 1; i < arr.length; i++) {
if (arr[minPos] > arr[i]) {
minPos = i;
}
}
//交换起始位置和最小值的位置
swap(arr, j, minPos);
}
}
static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
二、冒泡排序算法描述
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
- 针对所有的元素重复以上的步骤，除了最后一个；
- 重复步骤1~3，直到排序完成。
/**
* 冒泡排序算法：最好时间复杂度为O(n)、平均、最坏时间复杂度均为O(n²)，空间复杂度为1，稳定性：稳
*/
static void bubbleSort(int[] arr) {
for (int j = 0; j < arr.length; j++) {
//遍历数组，比较当前值和后一个值，如果当前值比后一个值大，则交换2个值的位置
for (int i = 0; i < arr.length - 1 - j; i++) {
if (arr[i] > arr[i + 1]) {
//交换2个元素的位置
swap(arr, i, i + 1);
}
}
}
}
三、插入排序算法描述
- 从第一个元素开始，该元素可以认为已经被排序；
- 取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置后；
- 重复步骤2~5。
/**
* 插入排序：最好时间复杂度为O(n)，平均、最坏时间复杂度为O(n²)，空间复杂度为1，稳定性：稳
*/
static void insertionSort(int[] arr) {
//从第一个元素开始，比较该元素与前一个元素
//如果该元素大于前一个元素，则将该元素放到该索引的位置，循换此步骤
for (int i = 1; i < arr.length; i++) {
//该数为递减
for (int j = i; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
//交换后一个元素和前一个元素的位置
swap(arr, j, j - 1);
} else {
break;
}
}
}
}
四、希尔排序（增量缩小排序）算法描述
- 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
- 按增量序列个数k，对序列进行k 趟排序；
- 每一趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。
注意：希尔排序可能改变数据原本顺序，所以不稳定
/**
* 希尔排序：改进的插入排序，最好时间复杂度O(n)，平均时间复杂度O(n^1.3)，最坏时间复杂度O(n²)，空间复杂度为1，稳定性：不稳
*/
static void shellSort(int[] arr) {
int h = 1;
while (h <= arr.length / 3) {
h = 3 * h + 1;
}
for (int gap = h; gap >= 1; gap = (gap - 1) / 3) {
for (int i = gap; i < arr.length; i++) {
for (int j = i; j >= gap; j -= gap) {
if (arr[j] < arr[j - gap]) {
swap(arr, j, j - gap);
}
}
}
}
}
五、归并排序（递归思想）算法描述
- 把长度为n的输入序列分成两个长度为n/2的子序列；
- 对这两个子序列分别采用归并排序；
- 将两个排序好的子序列合并成一个最终的排序序列。
/**
* 归并排序：最好、平均、最坏时间复杂度均为O(nlogn)，空间复杂度为O(n)，稳定性：稳
*/
static void mergeSort(int[] arr){
sort(arr,0 , arr.length - 1);
}
static void sort(int[] arr, int left, int right) {
//把数组切割然后调用merge排序，直到left==right为止
if(left == right) return;
//找出数组中间索引，将数组分成2段分别排序
int mid = left + (right - left) / 2;
sort(arr, left, mid);
sort(arr, mid + 1, right);
//将这2段数据进行排序归并
merge(arr, left, mid + 1, right);
}
static void merge(int[] arr, int left, int right, int rightBound) {
//将一个数组分为2段，把每一段数组进行排序
int mid = right - 1;
int[] temp = new int[rightBound - left + 1];
//左边数组起点
int leftPtr = left;
//右边数组起点
int rightPtr = right;
//新数组起点
int k = 0;
while (leftPtr <= mid && rightPtr <= rightBound) {
temp[k++] = arr[leftPtr] <= arr[rightPtr] ? arr[leftPtr++] : arr[rightPtr++];
}
//将剩下的数组直接放到temp中
while (leftPtr <= mid) temp[k++] = arr[leftPtr++];
while (rightPtr <= rightBound) temp[k++] = arr[rightPtr++];
//temp完成后给传入的数组赋值
System.arraycopy(temp, 0, arr, left, temp.length);
}
六、快速排序算法描述
- 从数列中挑出一个元素，称为 “基准”（pivot）；
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
/**
* 快速排序：最好、平均时间复杂度均为O(nlogn)，最坏时间复杂度为O(n²)，空间复杂度为O(logn)，稳定性：不稳
*/
static void quickSort(int[] arr, int leftPtr, int rightBound) {
if(leftPtr >= rightBound) return;
//定义轴的索引
int pivotIndex = partition(arr, leftPtr, rightBound);
quickSort(arr, leftPtr, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, rightBound);
}
static int partition(int[] arr, int leftPtr, int rightBound) {
//以最右边的数为轴,数组两段同时向中间挤压
int pivot = arr[rightBound];
int leftIndex = leftPtr;
int rightIndex = rightBound - 1;
//注意：这里的等于是为了最后索引交汇时，把leftIndex移到rightBound的位置
while (leftIndex <= rightIndex) {
//从左边开始，找到比轴数大的数为止
while (leftIndex <= rightIndex && arr[leftIndex] <= pivot) leftIndex++;
//从右边开始，找到比轴数小的数为止
while (leftIndex <= rightIndex && arr[rightIndex] > pivot) rightIndex--;
//如果索引没有交叉，则交换两个位置的数
if(leftIndex < rightIndex) swap(arr, leftIndex, rightIndex);
}
//将轴上的值放到该数本该处的位置
swap(arr, leftIndex, rightBound);
return leftIndex;
}
七、计数排序算法描述
- 找出待排序的数组中最大和最小的元素；
- 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
- 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
- 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
/**
* 计数排序：最好、平均、最坏时间复杂度均为O(n + k)，空间复杂度为O(n + k)，稳定性：稳
*/
static void countingSort(int[] arr) {
int bucketLen = findMax(arr) + 1;
int[] bucket = new int[bucketLen];
//count中，下标即为数字本身，下标上的值即为该数字的数量
for (int value : arr) {
bucket[value]++;
}
int sortedIndex = 0;
for (int j = 0; j < bucketLen; j++) {
//将计数数组挨个递减直到0为止
while (bucket[j] > 0) {
//把原数组重新赋值
arr[sortedIndex++] = j;
//赋值后计数数组当前索引上的值自减
bucket[j]--;
}
}
}
static int findMax(int[] arr) {
int result = arr[0];
for (int i = 0; i < arr.length; i++) {
result = Math.max(result, arr[i]);
}
return result;
}
八、基数排序算法描述
- 取得数组中的最大数，并取得位数；
- arr为原始数组，从最低位开始取每个位组成radix数组；
- 对radix进行计数排序（利用计数排序适用于小范围数的特点）；
/***
* 基数排序：最好、平均、最坏时间复杂度均为O(n * k)，空间复杂度为O(n + k)，稳定性：稳
* @return
*/
static int[] radixSort(int[] arr, int maxDigit) {
int mod = 10;
int dev = 1;
//最高有几位就循环几次
for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
// 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
int[][] counter = new int[mod * 2][0];
for (int j = 0; j < arr.length; j++) {
int bucket = ((arr[j] % mod) / dev) + mod;
counter[bucket] = arrayAppend(counter[bucket], arr[j]);
}
int pos = 0;
for (int[] bucket : counter) {
for (int value : bucket) {
arr[pos++] = value;
}
}
}
return arr;
}
/**
* 自动扩容，并保存数据
*
* @param arr
* @param value
*/
static int[] arrayAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
return arr;
}
/**
* 获取最高位数
*/
static int getMaxDigit(int[] arr) {
int maxValue = findMax(arr);
return getNumLenght(maxValue);
}
//获取数字位数，几位数
static int getNumLenght(long num) {
if (num == 0) {
return 1;
}
int lenght = 0;
for (long temp = num; temp != 0; temp /= 10) {
lenght++;
}
return lenght;
}
九、桶排序算法描述
- 设置一个定量的数组当作空桶；
- 遍历输入数据，并且把数据一个一个放到对应的桶里去；
- 对每个不是空的桶进行排序；
- 从不是空的桶里把排好序的数据拼接起来。
/***
* 桶排序：最好时间复杂度均为O(n)，平均时间复杂度均为O(n + k)，最坏时间复杂度均为O(n²)，空间复杂度为O(n + k)，稳定性：稳
*/
static int[] bucketSort(int[] arr, int bucketSize) {
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] = arrayAppend(buckets[index], arr[i]);
}
int arrIndex = 0;
for (int[] bucket : buckets) {
if (bucket.length <= 0) {
continue;
}
// 对每个桶进行排序，这里使用了插入排序
bucket = insertionSort(bucket);
for (int value : bucket) {
arr[arrIndex++] = value;
}
}
return arr;
}
