​

 💎所属专栏：数据结构与算法学习 

💎 欢迎大家互三：2的n次方_

 

🍁1. 插入排序

🍁1.1 直接插入排序

插入排序是一种简单直观的排序算法，它的原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

以从小到大排序为例

1.从第一个元素开始，可以看作是有序的元素

2.取出下一个元素，与前面已经排好序的元素比较，如果前面的元素大于此元素，就把前面的元素往后移，继续往前找，找到小于或等于的位置进行插入，直到找到最前面

​

<code>public class InsertSort {

public static void main(String[] args) {

int[] arr = {5, 1, 2, 4, 3};

insertSort(arr);

System.out.println(Arrays.toString(arr));

}

public static void insertSort(int[] arr) {

for (int i = 1; i < arr.length; i++) {

int tmp = arr[i];

int j = i - 1;

//比tmp大的元素往后移

for (; j >= 0 && arr[j] > tmp; j--) {

arr[j + 1] = arr[j];

}

arr[j + 1] = tmp;

}

}

}

🍁1.2 希尔排序

希尔排序的基本思想是：

先选定一个整数，把待排序的数据分为多个组，对每一个组内进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

​

假设有一个数组<code>arr = [9, 8, 3, 7, 5, 6, 4, 1]，我们采用最简单的增量序列（每次减半）来进行希尔排序：

1. 初始增量d = 4，将数组分为4组，每组进行插入排序：[9, 7], [8, 5], [3, 6], [4, 1]

2. 增量d = 2，将数组分为2组，每组进行插入排序：[7, 5, 6, 1], [9, 8, 3, 4]

3. 增量d = 1，整个数组作为一组进行插入排序，得到最终结果：[1, 3, 4, 5, 6, 7, 8, 9]

public static void shellSort(int[] arr) {

int gap = arr.length;

//增量每次减半

while (gap > 1) {

gap /= 2;

shell(arr, gap);

}

}

private static void shell(int[] arr, int gap) {

for (int i = gap; i < arr.length; i++) {

int tmp = arr[i];

int j = i - gap;

//比tmp大的元素往后移

for (; j >= 0 && arr[j] > tmp; j -= gap) {

arr[j + gap] = arr[j];

}

arr[j + gap] = tmp;

}

}

🍁2. 选择排序

🍁2.1 直接选择排序

直接选择排序的思想：

每次从待排序的数据中选择一个最小（最大）的元素放在序列起始位置，直到整个序列元素排序完毕

​

<code> public static void selectSort(int[] arr) {

for (int i = 0; i < arr.length; i++) {

int minIndex = i;

for (int j = i + 1; j < arr.length; j++) {

if (arr[j] < arr[minIndex]) {

minIndex = j;

}

}

swap(arr, i, minIndex);

}

}

🍁2.2 堆排序

堆排序在上一节中已经有过介绍，这里再简单回顾下，还是以从小到大排序为例，这时我们创建一个大根堆，堆顶元素也就是最大的，把最顶元素和堆尾元素进行交换，接着向下调整，再把堆顶元素和堆尾元素进行交换，也就是排在了上一个最大元素的前面，重复此过程，就实现了从小到大排序。

 上一篇回顾

public static void heapSort(int[] arr) {

createHeap(arr);

int end = arr.length - 1;

while (end > 0) {

//堆顶和end元素互换

swap(arr, 0, end);

//向下调整

siftDown(arr, 0, end);

end--;

}

}

public static void createHeap(int[] arr) {

for (int parent = (arr.length - 1 - 1) / 2; parent >= 0; parent--) {

siftDown(arr, parent, arr.length);

}

}

private static void siftDown(int[] arr, int parent, int length) {

int child = 2 * parent + 1;

while (child < length) {

if (child + 1 < length && arr[child] < arr[child + 1]) {

child += 1;

}

if (arr[child] > arr[parent]) {

swap(arr, child, parent);

child = 2 * child + 1;

} else {

break;

}

}

}

🍁3. 交换排序

🍁3.1 冒泡排序

冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。

比较每一对相邻的元素：如果第一个比第二个大（升序排序），就交换它们两个，这步做完后，最后的元素会是最大的数。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

​

<code> public static void bubbleSort(int[] arr) {

for (int i = 0; i < arr.length - 1; i++) {

boolean flag = false;

for (int j = 0; j < arr.length - 1 - i; j++) {

if (arr[j] > arr[j + 1]) {

swap(arr, j, j + 1);

flag = true;

}

}

//如果这一趟没有交换任何一对元素，表示已经排好序了

if(!flag){

break;

}

}

}

 这里做了一个优化，如果给出的数据只有一对数据不符合顺序，那么交换这对数据之后就不用再重复后续的程序了，所以直接结束循环即可，在一些情况下，通过这种优化，冒泡排序的时间复杂度可以达到O(n)

🍁3.2 快速排序

首先把0索引的位置当作基准数，定义两个指针，先将右指针从数组末尾开始往前找，遇到比基准数小的停下来，左指针从1索引开始往后找，遇到比基准数大的停下来，交换左右指针的数，重复此过程，直到左右指针相遇，此时和基准数交换，就可以把基准数排到正确的位置，此时左边都是比基准数小的，右边都是比基准数大的，再依次递归基准数左边部分和右边部分，就实现了排序

注意：一定要先从右边开始找比基准数小的，先从左边开始就无法达到效果

​

<code> public static void quickSort(int[] arr, int start, int end) {

if (start >= end) {

return;

}

int mid = part(arr, start, end);

quickSort(arr, start, mid - 1);

quickSort(arr, mid + 1, end);

}

public static int part(int[] arr, int i, int j) {

int tmp = arr[i];

int tmpStart = i;

while (i < j) {

while (i < j && arr[j] >= tmp) {

j--;

}

while (i < j && arr[i] <= tmp) {

i++;

}

swap(arr, i, j);

}

swap(arr, tmpStart, i);

return i;

}

 关于基准数归位的过程还有一种优化的方法，由于上面使用了大量的交换，也会浪费一些时间

public static int part1(int[] arr, int i, int j) {

int tmp = arr[i];

while (i < j) {

while (i < j && arr[j] >= tmp) {

j--;

}

arr[i] = arr[j];

while (i < j && arr[i] <= tmp) {

i++;

}

arr[j] = arr[i];

}

arr[i] = tmp;

return i;

}

也就是先把基准数拿出来，这时就留出来一个空位，接着从右边找比基准数小的，填上空位，再从左边找比基准数大的，再填上右边的空位，以此类推

还有一个优化的点是，输入数组已经是有序（升序或降序）的，或者每次划分（partition）操作都选择到最小（或最大）的元素作为基准（pivot），导致每次划分只将一个元素移到它最终的位置上，而其他所有元素都留在原数组的另一侧。这种情况下，每次划分后的递归调用处理的子数组大小几乎相同，递归的深度接近n，导致总的比较和交换次数接近n^2。

 下面通过三数取中法来更换基准数进行优化

private static int getMid(int[] arr, int left, int right) {

int mid = (left + right) / 2;

if (arr[left] > arr[right]) {

if (arr[mid] > arr[left]) {

return left;

} else if (arr[mid] < arr[right]) {

return right;

} else {

return mid;

}

} else {

if (arr[mid] > arr[right]) {

return right;

} else if (arr[mid] < arr[left]) {

return left;

} else {

return mid;

}

}

}

 获取中位数之后进行交换：

​

 另一个可以优化的是，由于快速排序的递归是一棵二叉树，每一层都是指数级的增长，所以最后两层会有很多递归需要走，但此时元素也趋于有序，就可以调用插入排序

<code> if(end - start + 1 <= 3){

insertSort(arr,start,end);

return;

}

非递归实现

递归需要一直在栈上开辟空间，容易造成栈溢出，这里我们直接通过栈来进行非递归的实现

public static void yquickSort(int[] arr,int start,int end){

Stack<Integer> stack = new Stack<>();

int pivot = part1(arr,start,end);

if(pivot > start + 1){

stack.push(start);

stack.push(pivot - 1);

}

if(pivot < end - 1){

stack.push(pivot + 1);

stack.push(end);

}

while(!stack.isEmpty()){

end = stack.pop();

start = stack.pop();

pivot = part1(arr,start,end);

if(pivot > start + 1){

stack.push(start);

stack.push(pivot - 1);

}

if(pivot < end - 1){

stack.push(pivot + 1);

stack.push(end);

}

}

}

 🍁4. 归并排序

归并排序主要利用了分治法，先使每个子序列有序，再使子序列段间有序，组后合并分解的子序列

​

 首先把要排序的数组依次分解，直到两两一组，之后开始合并，合并的过程也就是把两个有序数组再合并为一个有序数组的过程，每次取出两个数组的较小者存入合并的数组中，最终合并为一整个数组

<code> public static void mergeSort(int[] arr, int left, int right) {

if (left >= right) return;

int mid = (left + right) / 2;

mergeSort(arr, left, mid);

mergeSort(arr, mid + 1, right);

merge(arr, left, mid, right);

}

//也就是合并两个有序数组

public static void merge(int[] arr, int left, int mid, int right) {

int[] tmp = new int[right - left + 1];

int k = 0;

int s1 = left;

int s2 = mid + 1;

//将分解后的两个数组每次取出最小值放在tmp数组中

while (s1 <= mid && s2 <= right) {

if (arr[s1] >= arr[s2]) {

tmp[k++] = arr[s2++];

} else {

tmp[k++] = arr[s1++];

}

}

while (s1 <= mid) {

tmp[k++] = arr[s1++];

}

while (s2 <= right) {

tmp[k++] = arr[s2++];

}

for (int i = 0; i < k; i++) {

arr[left + i] = tmp[i];

}

}

 非递归实现归并排序

 非递归实现也就是通过循环来模拟递归，依次合并数组，gap取

public static void mergeSortNor(int[] arr) {

int gap = 1;

while (gap < arr.length) {

for (int i = 0; i < arr.length; i += gap * 2) {

int left = i;

int mid = i + gap - 1;

if (mid >= arr.length) {

mid = arr.length - 1;

}

int right = mid + gap;

if (right >= arr.length) {

right = arr.length - 1;

}

merge(arr, left, mid, right);

}

gap *= 2;

}

}

🍁5. 计数排序

计数排序是一种基于非比较的排序算法，计数排序的主要特点是通过统计每个元素出现的次数，来确定每个元素在排序后数组中的位置，从而实现排序。

​

 计算出以上数据出现的次数之后，再根据次数进行遍历，就可以达到排序的效果

<code> public static void countSort(int[] arr) {

int maxVal = arr[0];

int minVal = arr[0];

//找到最大值和最小值

for (int i = 0; i < arr.length; i++) {

if (arr[i] > maxVal) {

maxVal = arr[i];

}

if (arr[i] < minVal) {

minVal = arr[i];

}

}

int[] tmp = new int[maxVal - minVal + 1];

//开始计数

for (int i = 0; i < arr.length; i++) {

tmp[arr[i] - minVal]++;

}

int index = 0;

//将数据赋值给数组

for (int i = 0; i < tmp.length; i++) {

while (tmp[i]-- != 0) {

arr[index] = i + minVal;

index++;

}

}

}