前言
忙里偷闲，顺手整理一下十大排排序算法。
冒泡排序
步骤说明：
- 1.比较相邻的2个元素，如果第一个比第二个大，就交换他们的位置。
- 2.对每一对相邻元素做同样的操作，从开始第一对到结尾的最后一对，这步骤完成后，最后的元素会是最大的元素。
- 3.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
代码示例
public class BubbleSort extends BaseSort {
public BubbleSort(int[] nums) {
super(nums);
}
@Override
public int[] sort() {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - 1; j++) {
if (arr[j] > arr[j + 1]) {
super.swap(arr, j, j + 1);
}
}
}
return arr;
}
}
选择排序
步骤说明：
- 1.首先在未排序的序列中找到最小/大的元素，存放到排序序列的起始位置。
- 2.再从剩余未排序元素中继续寻找最小/大的元素，然后放到已排序序列的末尾。
- 3.重复2步骤，知道所有元素均排序完毕.
代码示例
public class SelectionSort extends BaseSort {
public SelectionSort(int[] nums) {
super(nums);
}
@Override
public int[] sort() {
//总共要进行n-1次比较
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
//记录最小元素下标
min = j;
}
}
//交换最小值和i的位图
if (i != min) {
swap(arr, i, min);
}
}
return arr;
}
}
插入排序
步骤说明：
- 1.将第一待排序序列的第一个元素看做是一个有序的序列，把第二个元素到最后一个元素当成是未排序的序列。
- 2.从头到尾依次扫描未排序的序列，将扫描到的每个元素插入有序序列的适当位置，
- 3.如果待插入的元素与有序序列中的某个元素相等，则将待插入的元素插入到相等元素的后面。
代码示例
public class InsertSort extends BaseSort {
public InsertSort(int[] nums) {
super(nums);
}
@Override
public int[] sort() {
for (int i = 1; i < arr.length; i++) {
int tmp = arr[i];
int j = i;
while (j > 0 && tmp < arr[j - 1]) {
arr[j] = arr[j -1];
j--;
}
if (j != i) {
arr[j] = tmp;
}
}
return arr;
}
}
希尔排序
步骤说明：
- 1.选择一个增量序列，t1, t2, ....... , tk,其中 ti>tj, tk = 1。
- 2.按增量序列个数k，对序列进行k躺排序。
- 3.每趟排序，根据对应的增量ti, 将待排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序，仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。
代码示例
public class ShellSort extends BaseSort {
public ShellSort(int[] nums) {
super(nums);
}
@Override
public int[] sort() {
int gap = 1;
while (gap < arr.length) {
gap = gap * 3 + 1;
}
while (gap > 0) {
for (int i = 0; i < arr.length; i++) {
int temp = arr[i];
int j = i - gap;
while (j >= 0 && arr[j] > temp) {
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = temp;
}
gap = (int) Math.floor(gap / 3);
}
return arr;
}
}
归并排序
步骤说明：
- 1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列。
- 2.设定两个指针，最初位置分别为两个已经排序序列的起始位置。
- 3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一个位置。
- 4.重复步骤3直到某一指针达到序列尾部。
- 5.将另一个序列剩下的所有元素直接复制到合并队列的尾部。
代码示例
public class MergeSort extends BaseSort{
public MergeSort(int[] nums) {
super(nums);
}
@Override
public int[] sort() {
return mergeSort(arr);
}
public int[] mergeSort(int[] nums) {
if (nums.length < 2) {
return nums;
}
int middle = (int) Math.floor(nums.length / 2);
int[] left = Arrays.copyOfRange(nums, 0, middle);
int[] right = Arrays.copyOfRange(nums, middle, nums.length);
return merge(mergeSort(left), mergeSort(right));
}
private int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
int i = 0;
while (left.length > 0 && right.length > 0) {
if (left[0] <= right[0]) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1 , left.length);
} else {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
}
while (left.length > 0) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
}
while (right.length > 0) {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
return result;
}
}
快速排序
步骤说明：
- 1.从数列中挑出一个元素，称为基准（pivot）。
- 2.重新排序数列，所有元素比基准小的，全部放到基准前边，比基准大的全部放到基准后面（如果与基准相等，可以放到任意一边）。在这个分区退出之后，该基准就处于数列的中间位置，也就是分区操作，每个分区被称做一个 partition。
- 3.递归排序两个 partition。
代码示例
public class QuickSort extends BaseSort {
public QuickSort(int[] nums) {
super(nums);
}
@Override
public int[] sort() {
return quickSort(arr, 0, arr.length - 1);
}
public int[] quickSort(int[] nums, int left, int right) {
if (left < right) {
int partition = partition(nums, left, right);
quickSort(nums, left, partition - 1);
quickSort(nums, partition + 1, right);
}
return nums;
}
public int partition(int[] nums, int left, int right) {
int pivot = left;
int index = pivot + 1;
for (int i = index; i <= right; i++) {
if (nums[i] < nums[pivot]) {
swap(nums, i, index);
index++;
}
}
swap(nums, pivot, index - 1);
return index - 1;
}
}
堆排序
步骤说明：
- 1.创建一个heap， H[0....n-1] .
- 2.把堆首（最大值）和堆尾互换。
- 3.把堆的大小缩小1，并调用 shift_down(0) ,目的是把新的数组顶端数据调整到相应的位置。
- 4.重复步骤2，直到到堆的大小变为1。
代码示例
public class HeapSort extends BaseSort {
public HeapSort(int[] nums) {
super(nums);
}
@Override
public int[] sort() {
int len = arr.length;
bulidMaxHeap(arr, len);
for (int i = len - 1; i > 0; i--) {
swap(arr, 0, i);
len--;
heapify(arr, 0, len);
}
return arr;
}
public void bulidMaxHeap(int[] nums, int len) {
for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
heapify(nums, i, len);
}
}
private void heapify(int[] nums, int i, int len) {
int left = (2 * i) + 1;
int right = (2 * i) + 2;
int last = i;
if (left < len && nums[left] > nums[last]) {
last = left;
}
if (right < len && nums[right] > nums[last]) {
last = right;
}
if (last != i) {
swap(nums, i, last);
heapify(nums, last, len);
}
}
}
计数排序
步骤说明：
- 1.在 O(n) 的时间扫描一下整个序列 a，找到序列中最大值 ***max *** 和最小值 min 。
- 2.开辟一块新的空间创建新的数组 b*，长度为 max-min+1。
- 3.数字 b 中的 index 的元素记录的值是a中元素的出现次数。
- 4.最后输出目标整数序列，具体的逻辑是遍历数组b，输出相应元素以及对应的个数。
代码示例
public class CountSort extends BaseSort{
public CountSort(int[] nums) {
super(nums);
}
@Override
public int[] sort() {
return countSort(arr, getMaxValue(arr));
}
public int[] countSort(int[] nums, int max) {
int bucketLen = max + 1;
int[] bucket = new int[bucketLen];
for (int i : nums) {
bucket[i]++;
}
int sortedIndex = 0;
for (int i = 0; i < bucketLen; i++) {
while (bucket[i] > 0) {
nums[sortedIndex++] = i;
bucket[i]--;
}
}
return nums;
}
public int getMaxValue(int[] nums) {
int maxValue = arr[0];
for (int i : nums) {
if (maxValue < i) {
maxValue = i;
}
}
return maxValue;
}
}
桶排序
步骤说明：
- 1.设置固定数量的空桶。
- 2.把数据放到对应的桶中。
- 3.对每个不为空的桶进行排序。
- 4.拼接不为空的桶的数据。
代码示例
public class BucketSort extends BaseSort {
public BucketSort(int[] nums) {
super(nums);
}
@Override
public int[] sort() {
return bucketSort(arr, 5);
}
public int[] bucketSort(int[] nums, int bucketSize) {
if (nums.length == 0) {
return nums;
}
int maxValue = nums[0];
int minValue = nums[0];
for (int i : nums) {
if (i < minValue) {
minValue = i;
} else if (i > maxValue) {
maxValue = i;
}
}
int bucketCount = (int) (Math.floor((maxValue - minValue) / bucketSize) + 1);
int[][] buckets = new int[bucketCount][0];
for (int i = 0; i < nums.length; i++) {
int index = (int) Math.floor((nums[i] - minValue) / bucketCount);
buckets[index] = appendBucket(buckets[index], nums[i]);
}
int arrIndex = 0;
for (int[] bucket : buckets) {
if (bucket.length <= 0) {
continue;
}
//对每个桶进行插入排序
InsertSort insertSort = new InsertSort(bucket);
bucket = insertSort.sort();
for (int i : bucket) {
nums[arrIndex++] = i;
}
}
return nums;
}
/**
* 自动扩容并保存数据
* @param bucket
* @param num
* @return
*/
private int[] appendBucket(int[] bucket, int num) {
bucket = Arrays.copyOf(bucket, bucket.length + 1);
bucket[bucket.length - 1] = num;
return bucket;
}
}
计数排序
步骤说明：
- 1.将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数据前面补零。
- 2.从最低位开始，依次进行一次排序。
- 3.从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
代码示例
public class RadixSort extends BaseSort{
public RadixSort(int[] nums) {
super(nums);
}
@Override
public int[] sort() {
return radixSort(arr, getMaxDigit(arr));
}
public int[] radixSort(int[] nums, int maxDigit) {
int mod = 10;
int dev = 1;
for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
int[][] counter = new int[mod * 2][0];
for (int j = 0; j < nums.length; j++) {
int bucket = ((nums[j] % mod) / dev) + mod;
counter[bucket] = arrayAppend(counter[bucket], nums[j]);
}
int pos = 0;
for (int[] bucket : counter) {
for (int value : bucket) {
nums[pos++] = value;
}
}
}
return nums;
}
private int[] arrayAppend(int[] ints, int num) {
ints = Arrays.copyOf(ints, ints.length + 1);
ints[ints.length - 1] = num;
return ints;
}
/**
* 获取最高位数
* @param nums
* @return
*/
public int getMaxDigit(int[] nums) {
int maxValue = getMaxValue(nums);
return getNumLenght(maxValue);
}
private int getNumLenght(int maxValue) {
if (maxValue == 0) {
return 1;
}
int length = 0;
for (long tmp = maxValue; tmp != 0; tmp /= 10) {
length++;
}
return length;
}
private int getMaxValue(int[] nums) {
int maxValue = nums[0];
for (int i : nums) {
if (maxValue < i) {
maxValue = i;
}
}
return maxValue;
}
}
BaseSort类
public abstract class BaseSort {
protected int[] arr;
public BaseSort(int[] nums) {
arr = Arrays.copyOf(nums, nums.length);
}
public void swap(int[] nums, int a, int b) {
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
public void execute() {
long t1 = System.currentTimeMillis();
int[] a = sort();
System.out.println("耗时啊：" + (System.currentTimeMillis() - t1) + "ms");
print(a);
}
private void print(int[] a) {
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}
public abstract int[] sort();
}
总结
排序算法可以分为内部排序和外部排序两种。
-
内部排序：是指数据在内存中进行排序。
-
外部排序：因排序数据很大，一次不能排序所有记录，在排序过程中要访问外存。
| 排序算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 排序方式 | 稳定性 |
|---|---|---|---|---|---|---|
| 冒泡排序 | $O(n^2)$ | $O(n)$ | $O(n^2)$ | $O(1)$ | In-place | 稳定 |
| 选择排序 | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | In-place | 不稳定 |
| 插入排序 | $O(n^2)$ | $O(n)$ | $O(n^2)$ | $O(1)$ | In-place | 稳定 |
| 希尔排序 | $O(n log n)$ | $O(n log^2 n)$ | $O(n log^2 n$) | $O(1)v | In-place | 不稳定 |
| 归并排序 | $O(n log n)$ | $O(n log n)$ | $O(n log n)$ | $O(n)$ | Out-place | 稳定 |
| 快速排序 | $O(n log n)$ | $O(n log n)$ | $O(n^2)$ | $O(log n)$ | In-place | 不稳定 |
| 堆排序 | $O(n log n)$ | $O(n log n)$ | $O(n log n)$ | $O(1)$ | In-place | 不稳定 |
| 计数排序 | $O(n + k)$ | $O(n + k)$ | $O(n + k)$ | $O(k)$ | Out-place | 稳定 |
| 桶排序 | $O(n + k)$ | $O(n + k)$ | $O(n^2)$ | $O(n + k)$ | Out-place | 稳定 |
| 基数排序 | $O(n * k)$ | $O(n * k)$ | $O(n * k)$ | $O(n + k)$ | Out-place | 稳定 |
- 写作不易，转载请注明出处，喜欢的小伙伴可以关注公众号查看更多喜欢的文章。
- 联系方式：4272231@163.com
- QQ:95472323
- 微信:ffj2000