部分内容来源：bilibili，JavaGuide
冒泡排序
冒泡排序是一种简单的排序算法。它重复地遍历要排序的序列，依次比较两个元素，如果它们的顺序错误就把它们交换过来。
遍历序列的工作是重复地进行直到没有再需要交换为止，此时说明该序列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢 “浮” 到数列的顶端
不断地比较交换，不断地将大的元素往后移
算法步骤
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
- 针对所有的元素重复以上的步骤，除了最后一个；
- 重复步骤 1~3，直到排序完成
图解算法
不断地交换，把大的往后移
我们每次是j和j+1比，我们每次会排序号好，也就是最后面有i个排序好的最大的数
所以我们的j的范围是，j<arr.length-i
/**
* 冒泡排序
* @param arr
* @return arr
*/
public static int[] bubbleSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
for (int j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
return arr;
}算法分析
- 稳定性：稳定
- 时间复杂度：最佳：$O(n)$ ，最差：$O(n^2)$， 平均：$O(n^2)$
- 空间复杂度：$O(1)$
- 排序方式：In-place
我的手写代码
package com.example.threadpool.Sort;
public class BubbleSort {
public static void main(String[] args) {
int[] nums=new int[]{3,5,9,8,7,6,2,1,4};
bubbleSort(nums);
for (int num:nums){
System.out.print(num);
}
}
public static void bubbleSort(int[] nums){
int n=nums.length;
for(int i=1;i<n;i++){
for (int j=0;j<n-i;j++)
{
if(nums[j]>nums[j+1]){
int temp=nums[j];
nums[j]=nums[j+1];
nums[j+1]=temp;
}
}
}
}
}快速排序
快速排序的基本思想
快速排序用到了分治思想，同样的还有归并排序。
乍看起来快速排序和归并排序非常相似，都是将大问题分解成一个一个小问题
先排序子串，最后合并
不同的是快速排序在划分子问题的时候经过多一步处理，将划分的两组数据划分为一大一小，这样在最后合并的时候就不必像归并排序那样再进行比较。但也正因为如此，划分的不定性使得快速排序的时间复杂度并不稳定。
快速排序的基本思想：
通过一趟排序将待排序列分隔成独立的两部分，其中一部分记录的元素均比另一部分的元素小，则可分别对这两部分子序列继续进行排序，以达到整个序列有序。
算法步骤
快速排序使用分治法（Divide and conquer）策略来把一个序列分为较小和较大的 2 个子序列，然后递归地排序两个子序列。具体算法描述如下：
- 从序列中随机挑出一个元素，做为 “基准”(
pivot)； - 重新排列序列，将所有比基准值小的元素摆放在基准前面，所有比基准值大的摆在基准的后面（相同的数可以到任一边）。 在这个操作结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地把小于基准值元素的子序列和大于基准值元素的子序列进行快速排序。
图解算法
我们指到数组的第一个元素，让它作为我们的基准元素
然后我们第一次排序完把元素划分成了两端，左边的比比基准元素小，右边的比基准元素大
快速排序是确保基准在正确的位置
例如我们比基准小的在左边，比基准大的在右边，这并不是基准左右排序好了，而是基准处在了正确的位置
我们要找的是第一个大于基准点的元素
算法+解析
//采用分治思想
public static int partition(int[] array, int low, int high) {
//把pivot作为我们的基准点,high的位置是我们的基准点，array【high】是基准点
int pivot = array[high];
//是指针下标,用来移动的
int pointer = low;
//遍历当前分区的数组，从下标 low 到 high - 1（注意，不包括 high，因为 high 是基准点 pivot 的位置）
//i 是当前被检查的元素的下标
for (int i = low; i < high; i++) {
//如果比我们的基准小，那么就交换位置
//如果是大于，就不做操作
//如果我们没进入if条件，就说明我们此时这个pointer的位置的值是从左往右找到的第一个大于基准的元素
//我们记录这个位置，然后i继续往右找，找到小于基准的值和这个位置交换，
//我们的pointer继续++，继续找到我们的从左往右大于基准的第一个元素
if (array[i] <= pivot) {
int temp = array[i];
array[i] = array[pointer];
array[pointer] = temp;
pointer++;
}
System.out.println(Arrays.toString(array));
}
//此时，数组已经通过 for 循环将所有 小于或等于基准点的元素 放到了数组左边区域，
//而 pointer 指向的是第一个 大于基准点的元素 的位置
//我们array[high]是我们的基准点，我们此时的array[pointer]是我们的第一个大于基准点的元素
//也就是此时pointer之前,我们将基准点放到正确的位置
//我们一开始是用nums【right】作为我们的基准点的，我们将基准点nums【right】放到正确的位置
int temp = array[pointer];
array[pointer] = array[high];
array[high] = temp;
return pointer;
}
//快速排序
public static void quickSort(int[] array, int low, int high) {
if (low < high) {
int position = partition(array, low, high);
quickSort(array, low, position - 1);
quickSort(array, position + 1, high);
}
}算法--精简
//快速排序
public static void quickSort(int[] array, int low, int high) {
if (low < high) {
int position = partition(array, low, high);
quickSort(array, low, position - 1);
quickSort(array, position + 1, high);
}
}
//分治思想
public static int partition(int[] array, int low, int high) {
int pivot = array[high]; //把pivot作为我们的基准点,high的位置是我们的基准点
int pointer = low; //是指针下标
for (int i = low; i < high; i++) {
if (array[i] <= pivot) {
int temp = array[i];
array[i] = array[pointer];
array[pointer] = temp;
pointer++;
}
System.out.println(Arrays.toString(array));
}
int temp = array[pointer];
array[pointer] = array[high];
array[high] = temp;
return pointer;
}
算法分析
- 稳定性：不稳定
- 时间复杂度：最佳：$O(nlogn)$， 最差：$O(n^2)$，平均：$O(nlogn)$
- 空间复杂度：$O(logn)$
我的手写代码
package com.example.threadpool.Sort;
public class QuickSort {
public static void main(String[] args) {
int nums[]=new int[]{
2,9,3,5,7,1,4,6
};
int left=0;
int right=nums.length;
quickSort(nums,left,right-1);
for(int num:nums){
System.out.print(num);
}
}
private static int partition(int [] nums,int left,int right){
int pivot=nums[right];//基准点
int pointer=left;//移动指针
for(int i=left;i<right;i++){
if(nums[i]<=pivot){//如果小于基准点,则交换位置
int temp=nums[i];
nums[i]=nums[pointer];
nums[pointer]=temp;
pointer++;
}
}
//此时pointer指向的是第一个的大于基准点的元素
//我们一开始是用nums【right】作为我们的基准点的，我们将基准点nums【right】放到正确的位置
int temp=nums[pointer];
nums[pointer]=nums[right];
nums[right]=temp;
return pointer;//返回基准的位置,基准就是排序好的单个数
}
public static void quickSort(int nums[],int left,int right){
if(left<right) {
int position = partition(nums, left, right);
quickSort(nums, left, position - 1);
quickSort(nums, position + 1, right);
}
}
}
选择排序
选择排序是一种简单直观的排序算法，无论什么数据进去都是 $O(n^2)$ 的时间复杂度。
所以用到它的时候，数据规模越小越好。
唯一的好处可能就是不占用额外的内存空间了吧。
它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
也就是我们选择最大OR最小的元素进行排序
算法步骤
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
- 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
- 重复第 2 步，直到所有元素均排序完毕。
图解算法
/**
* 选择排序
* @param arr
* @return arr
*/
public static int[] selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
int tmp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = tmp;
}
}
return arr;
}算法分析
- 稳定性：不稳定
- 时间复杂度：最佳：$O(n^2)$ ，最差：$O(n^2)$， 平均：$O(n^2)$
- 空间复杂度：$O(1)$
- 排序方式：In-place
我的手写代码
两层for循环，每次找到最小值，然后放到前面
package com.example.threadpool.Sort;
/**
* 选择排序
*/
public class SelectSort {
public static void main(String[] args) {
int[] nums=new int[]{3,5,9,8,7,6,2,1,4};
selectSort(nums);
for (int num:nums){
System.out.print(num);
}
}
public static void selectSort(int[] nums){
int n=nums.length;
for(int i=0;i<n;i++){
int minIndex=i;
for (int j = i+1; j <n ; j++) {
if(nums[j]<nums[minIndex]){
minIndex=j;
}
}
//说明下标发生变化,我们交换数字，选择最小的数到下标i的位置
if(minIndex!=i){
int temp=nums[i];
nums[i]=nums[minIndex];
nums[minIndex]=temp;
}
}
}
}插入排序
插入排序是一种简单直观的排序算法。
它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序在实现上，通常采用 in-place 排序（即只需用到 $O(1)$ 的额外空间的排序）
因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。
插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入
算法步骤
- 从第一个元素开始，该元素可以认为已经被排序；
- 取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置后；
- 重复步骤 2~5
图解算法
我们要记住上一个排序好的数组的最后一个元素的位置
然后我们不断向后，在排序好的数组里面插入元素
public static void InsertSelect(int[] nums){
int n=nums.length;
for(int i=1;i<n;i++){
//preIndex是排序好的数组的末尾位置
int preIndex=i-1;
//current是当前元素
int current=nums[i];
//我们在while循环中将元素不断向后移动
while(preIndex>=0&¤t<nums[preIndex]){
//我们向后移动一位
nums[preIndex+1]=nums[preIndex];
preIndex--;
}
//最终preIndex会停在我们要插入的元素的位置的后面一个位置
nums[preIndex+1]=current;
}我的手写代码
们要记住上一个排序好的数组的最后一个元素的位置
然后我们不断向后，在排序好的数组里面插入元素
我们找到比他小的元素就后移，比他大的就不动
package com.example.threadpool.Sort;
/**
* 插入排序
*/
public class InsertSort {
public static void main(String[] args) {
int[] nums=new int[]{3,5,9,8,7,6,2,1,4};
InsertSelect(nums);
for (int num:nums){
System.out.print(num);
}
}
public static void InsertSelect(int[] nums){
int n=nums.length;
for(int i=1;i<n;i++){
//preIndex是排序好的数组的末尾位置
int preIndex=i-1;
//current是当前元素
int current=nums[i];
//我们在while循环中将元素不断向后移动
while(preIndex>=0&¤t<nums[preIndex]){
//我们向后移动一位
nums[preIndex+1]=nums[preIndex];
preIndex--;
}
//最终preIndex会停在我们要插入的元素的位置的后面一个位置
nums[preIndex+1]=current;
}
}
}希尔排序
希尔排序是希尔 (Donald Shell) 于 1959 年提出的一种排序算法。
希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本
也称为递减增量排序算法，同时该算法是冲破 $O(n^2)$ 的第一批算法之一。
希尔排序的基本思想：
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序
待整个序列中的记录 “基本有序” 时，再对全体记录进行依次直接插入排序
算法步骤
我们来看下希尔排序的基本步骤
图解算法
例如此时我们的gap=Length/2
我们的Length也就是元素总数量为8，所以我们的gap为2
也就是我们往后4个4个间隔为一组（Index和Index+4和（Index+4+4））为一组
也就是Index和Index+gap为一组
这样子我们就分了图上面的四组出来【7，2】【3，0】【5，8】【9，6】我们对每组分别进行插入排序
然后gap/2
然后继续分组gap分组进行插入排序
到最后gap=1的时候，也就是所有元素为一组，我们来一个总体的插入排序
我们先分组排序让它变的有序
然后gap==1的时候，我们对整个数组进行插入排序
希尔排序就是优化后的插入排序（数组越有序，插入排序效率越高）
和插入排序的不同在于，我们插入排序他是--，一个一个往后插入，而我们这种是间隔gap往后插入
/**
* 希尔排序
*
* @param arr
* @return arr
*/
public static int[] shellSort(int[] arr) {
int n = arr.length;
int gap = n / 2;
while (gap > 0) {
for (int i = gap; i < n; i++) {
int current = arr[i];
int preIndex = i - gap;
// Insertion sort
while (preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + gap] = arr[preIndex];
preIndex -= gap;
}
arr[preIndex + gap] = current;
}
gap /= 2;
}
return arr;
}算法分析
- 稳定性：不稳定
- 时间复杂度：最佳：$O(nlogn)$， 最差：$O(n^2)$ 平均：$O(nlogn)$
- 空间复杂度：$O(1)$
我的手写代码
package com.example.threadpool.Sort;
/**
* 希尔排序就是优化后的插入排序（数组越有序，插入排序效率越高）
* 和插入排序的不同在于，我们插入排序他是--，一个一个往后插入，而我们这种是间隔gap往后插入
*/
public class ShellSort {
public static void main(String[] args) {
int[] nums=new int[]{3,5,9,8,7,6,2,1,4};
shellSort(nums);
for (int num:nums){
System.out.print(num);
}
}
public static void shellSort(int[] nums){
int n=nums.length;
int gap=n/2;
while(gap>0){
for(int i=gap;i<n;i++){
int current=nums[i];
int preIndex=i-gap;
while (preIndex >= 0 && nums[preIndex] > current) {
nums[preIndex + gap] = nums[preIndex];
preIndex -= gap;
}
nums[preIndex + gap] = current;
}
gap=gap/2;
}
}
}归并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法 (Divide and Conquer) 的一个非常典型的应用。
归并排序是一种稳定的排序方法。
将已有序的子序列合并，得到完全有序的序列
即先使每个子序列有序，再使子序列段间有序。
若将两个有序表合并成一个有序表，称为 2 - 路归并。
和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 $O(nlogn)$ 的时间复杂度。代价是需要额外的内存空间。
归并排序通过递归的方式将数组分解为更小的部分
再将这些部分合并成一个有序的整体
每次合并都保证了结果的有序性，从而实现了高效排序
算法步骤
归并排序算法是一个递归过程，边界条件为当输入序列仅有一个元素时，直接返回，具体过程如下：
- 如果输入内只有一个元素，则直接返回，否则将长度为 $n$ 的输入序列分成两个长度为 $n/2$ 的子序列；
- 分别对这两个子序列进行归并排序，使子序列变为有序状态；
- 设定两个指针，分别指向两个已经排序子序列的起始位置；
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间（用于存放排序结果），并移动指针到下一位置；
- 重复步骤 3 ~ 4 直到某一指针达到序列尾；
- 将另一序列剩下的所有元素直接复制到合并序列尾
图解算法
分治思想，分成几组进行排序
然后两个两个合并我们的有序数组
一组的头部和另一组的头部进行比较
/**
* 归并排序
*
* @param arr
* @return arr
*/
public static int[] mergeSort(int[] arr) {
if (arr.length <= 1) {
return arr;
}
int middle = arr.length / 2;
int[] arr_1 = Arrays.copyOfRange(arr, 0, middle);
int[] arr_2 = Arrays.copyOfRange(arr, middle, arr.length);
return merge(mergeSort(arr_1), mergeSort(arr_2));
}
/**
* Merge two sorted arrays
*
* @param arr_1
* @param arr_2
* @return sorted_arr
*/
public static int[] merge(int[] arr_1, int[] arr_2) {
int[] sorted_arr = new int[arr_1.length + arr_2.length];
int idx = 0, idx_1 = 0, idx_2 = 0;
while (idx_1 < arr_1.length && idx_2 < arr_2.length) {
if (arr_1[idx_1] < arr_2[idx_2]) {
sorted_arr[idx] = arr_1[idx_1];
idx_1 += 1;
} else {
sorted_arr[idx] = arr_2[idx_2];
idx_2 += 1;
}
idx += 1;
}
if (idx_1 < arr_1.length) {
while (idx_1 < arr_1.length) {
sorted_arr[idx] = arr_1[idx_1];
idx_1 += 1;
idx += 1;
}
} else {
while (idx_2 < arr_2.length) {
sorted_arr[idx] = arr_2[idx_2];
idx_2 += 1;
idx += 1;
}
}
return sorted_arr;
}算法分析
- 稳定性：稳定
- 时间复杂度：最佳：$O(nlogn)$， 最差：$O(nlogn)$， 平均：$O(nlogn)$
- 空间复杂度：$O(n)$
我的手写代码
package com.example.transational;
public class MergeSort {
public static void main(String[] args) {
int[] nums = new int[]{3, 5, 9, 8, 7, 6, 2, 1, 4};
int left = 0;
int right = nums.length;
mergeSort(nums, left, right - 1);
for (int num : nums) {
System.out.print(num);
}
}
public static void mergeSort(int[] nums, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
//递归排序左右半部分
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
//合并已排序部分
merge(nums, left, mid, right);
}
}
public static void merge(int[] array, int left, int middle, int right) {
//计算子数组大小[0,1,2]
int n1 = middle - left + 1; //n1是[0,1],包括middle
int n2 = right - middle; //n2是[2]
//创建临时数组
int[] leftArray = new int[n1];
int[] rightArray = new int[n2];
//拷贝数据到临时数组
for (int i = 0; i < n1; i++)
leftArray[i] = array[left + i];
for (int j = 0; j < n2; j++)
rightArray[j] = array[middle + 1 + j]; //因为n2不包括middle,所以要middle+1+j
//合并临时数组
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2) {
if (leftArray[i] < rightArray[j]) {
array[k] = leftArray[i];
i++;
} else {
array[k] = rightArray[j];
j++;
}
k++;
}
//有时候n1拷贝完了n2没拷贝完,或者n2拷贝完了n1没拷贝完
//我们要拷贝剩余元素
while (i < n1) {
array[k] = leftArray[i];
i++;
k++;
}
while (j < n2) {
array[k] = rightArray[j];
j++;
k++;
}
}
}堆排序
逻辑
一开始先建好最大堆，从下往上开始构建最大堆
该元素的最大堆构建好后，我们把我们的堆顶放到最后，开始下一轮对某个元素进行最大堆构建
然后排序过的元素是上一轮的堆顶，这个元素我们放到最后不用参与下一轮排序，我们依次构建最大堆，然后就排序好了
大根堆
大根堆：所有的父亲都大于等于它的左右孩子
小根堆：所有的父亲都小于等于它的左右孩子
因为我们的堆是完全二叉树，所以非常适合使用顺序存储的结构
我们依次从上到下，从左到右存储按顺序一个一个存到数组里面，因为所有节点都是顺序的，所以并不会有空间上的浪费
我们的堆一般是从下标1开始存储的，而不是下标0
这个结构的好处是
我们的父节点下标索引×2就会得到左孩子的下标
我们的父节点下标索引×2+1就会得到右孩子的下标
然后我们的子节点除以2然后向下取整，就能得到父节点的下标
ps：这就是为什么我们从下标1开始存，我们会有这个规律可以使用
所以大根堆的特点是：arr【i】>=arr【2×i】和arr【2×i】+1
排序逻辑
从下往上建堆
我们要用堆的性质去排序，那我们就要把他变成堆
倒着将每个节点为根的子树调整成堆
我们要从最后一个非叶节点的下标开始，因为叶子节点没有子树，所以以它们为根的子树自然就是堆了
我们倒着一个一个检查我们的每个节点
我们倒着来能保证检查到某个节点的时候，他的左右孩子对应的子树都已经变成堆了
如果我们从上往下去处理，此时我们的子节点并不是堆，所以要经过大量复杂的处理
例如我们看看下标为5和10的节点是否满足堆
我们发现60>53这个节点已经是堆了，所以我们并不需要进行任何调整
然后我们看这个
我们发现48为根的子树也已经是堆了
然后我们看这个，这个子树并不是堆，所以我们要进行调整
我们交换
我们倒着一个一个检查我们的每个节点
我们倒着来能保证检查到某个节点的时候，他的左右孩子对应的子树都已经变成堆了
如果我们从上往下去处理，此时我们的子节点并不是堆，所以要经过大量复杂的处理
我们几点交换后要经过连续的改变
从上往下对堆进行排序
我们每次都把我们的堆顶元素放到最后，也就是根节点元素放到最后，我们和最后一个元素做交换
我们如此反复下去，这样子每一轮就能排序好一个元素
如果有n个元素，那我们就要经过n-1轮
剩下最后一个的时候就不用再排序了
之前排序过的我们不用弄，我们向下调整新的堆，然后不断往复
最终排序好了
我的手写代码
步骤：
1.建堆
2.从上往下进行排序，上一轮排序过的最大元素不参与下一轮排序
package com.example.threadpool.Sort;
public class HeapSort {
public static void heapSort(int[] arr) {
int n = arr.length;
// 构建最大堆
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 一个个交换元素
for (int i = n - 1; i > 0; i--) {
// 将堆顶元素（最大值）与当前未排序部分的最后一个元素交换
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 对剩余的元素重新调整为最大堆
heapify(arr, i, 0);
}
}
// 调整堆，使其满足最大堆的性质
//n表示当前处理的数组部分的长度
//i表示要调整节点的索引
private static void heapify(int[] arr, int n, int i) {
int largest = i; // 初始化根节点为最大值,largest是大节点的下标
int left = 2 * i + 1; // 左子节点
int right = 2 * i + 2; // 右子节点
// 如果左子节点比根节点大，则更新最大值的索引
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// 如果右子节点比当前最大值大，则更新最大值的索引
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// 如果最大值不是根节点，则交换根节点和最大值，并继续调整受影响的子树
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// 递归调整受影响的子树
heapify(arr, n, largest);
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
System.out.println("排序前的数组：");
for (int num : arr) {
System.out.print(num + " ");
}
//对元素进行n-1次的构造最大堆操作
heapSort(arr);
System.out.println("\n排序后的数组：");
for (int num : arr) {
System.out.print(num + " ");
}
}
}