八大排序算法（冒泡排序、快速排序、堆排序.....）

每坚持一天，offer就会离我更近一步🌹

冒泡排序

算法描述：从第一个元素开始，两两比较，如果前者比后者大，那么就将两者进行交换，这样每经过一次排序，都能找到一个最大的元素并且把它放在数组的最后。
稳定性：稳定
时间复杂度：O(N^2)
代码：

public static int[] bubbleSort(int[] arr){for (int i = 0; i < arr.length - 1; i++) {
//            比较次数要减去i，每比较一次都会把最大的排到最后for (int j = 0; j < arr.length - 1 - i; j++) {
//                如果前边元素比后边的元素大就交换if(arr[j+1] < arr[j]){int temp = arr[j+1];arr[j+1] = arr[j];arr[j] = temp;}}}return arr;}

选择排序

算法描述：在每一次排序时，先假设第一个元素是最小的，然后从第二个元素一直遍历到最后一个元素，如果找到比第一个小的元素就进行交换，否则不交换。第一次排序时，有序区间中只有一个元素；第二次排序，有序区间中有两个元素，依次递增，直到所有元素都有序
时间复杂度：O(N^2)
稳定性：不稳定
代码：

public static void selectSort(int[] arr){for(int i = 0;i < arr.length - 1;i++){
//            假设第一个元素是最小的int minIndex = i;for (int j = i+1; j < arr.length; j++) {
//                再从无序的元素中找到比arr[minIndex]小的元素，进行交换if (arr[j]<arr[minIndex]){int temp = arr[j];arr[j] = arr[minIndex];arr[minIndex] = temp;}}}}

插入排序

算法描述：，初始时，先把第一个元素看成是有序的，然后把未排序的元素一个一个插入到有序序列中。
时间复杂度：O(N^2)
稳定性：稳定

public static void insertSort(int[] arr){
//        将arr[0]看作是有序的，所以从arr[1]开始遍历for (int i = 1; i < arr.length; i++){
//        暂存待插入元素int inserted = arr[i];int j = i - 1;
//            从后往前开始比较，如果待插入元素更小就将有序元素后移for (; j >= 0 && inserted < arr[j]; j--) {arr[j+1] = arr[j];}
//        将待插入元素插入arr[j+1] = inserted;}}

希尔排序

改进了插入排序

public static void shellSort(int[] arr){int n = arr.length;for(int gap = n/2;gap > 0; gap /= 2){for (int i = gap; i < n; i++) {int inserted = arr[i];int j=i-gap;for (; j >= 0&&arr[j]>inserted; j-=gap) {arr[j+gap] = arr[j];}arr[j+gap] = inserted;}}}

快速排序

算法描述：选择第一个元素当哨兵，一个左指针一个右指针，左指针从左开始扫描，遇到比哨兵大的元素就停；右指针从右开始扫描，遇到比哨兵小的元素就停，然后交换两个元素，直到左指针和右指针相遇，并交换相遇处的元素和哨兵。然后分别进行左半部分和右半部分的排序，同样的过程。
时间复杂度：O(NlogN)
稳定性：不稳定
代码：

public static void quickSort(int[] arr,int begin,int end){if (begin > end) return;
//        第一个元素当作哨兵int pivot = arr[begin];int i = begin;int j = end;while (true){
//            从后往前找比哨兵小的while (arr[j] >= pivot && i < j)j--;
//            从前往后找比哨兵大的while (arr[i] <= pivot && i < j)i++;
//            两个指针相遇就暂停if (i >= j){break;}
//            指针相遇后交换元素int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
//          交换哨兵和指针相遇处的元素arr[begin] = arr[i];arr[i] = pivot;
//        对左半部分元素进行排序quickSort(arr,begin,i-1);
//        对右半部分元素进行排序quickSort(arr,i+1,end);}

计数排序

算法描述：从初始数组中选取一个最大的元素，用它来做辅助数组的长度，然后遍历初始数组，统计每一个元素出现的次数并保存到辅助数组中，然后遍历辅助数组，取出元素并覆盖初始数组即可。
时间复杂度：O(N)
空间复杂度：O(N)
适用于元素范围较小的数组
代码：

public static void countSort(int[] arr){int max = Integer.MIN_VALUE;
//        找出数组中最大的数for(int num:arr){if(num > max) max = num;}
//      初始化计数数组，统计每个元素所出现的次数int[] temp = new int[max+1];for(int i=0;i<arr.length;i++){temp[arr[i]]++;}
//      取出计数数组中的元素，覆盖原来的数组int k = 0;for(int i=0;i<temp.length;i++){for(int j = temp[i];j > 0;j--){arr[k++] = i;}}}

堆排序

算法描述：先根据给定数组建一个大根堆（小根堆也可以），然后每次取堆顶元素和堆尾元素进行交换，此时取下来的堆顶元素就是当前数组中最大的，然后再次维护堆的性质，执行n次之后数组即为有序。
时间复杂度：O(NlogN)（建堆的时间复杂度是O(N)，维护堆性质的时间复杂度是O(logN)）
稳定性：不稳定
代码：

//    堆排序入口public static void heapSort(int[]arr){int n = arr.length;//建立堆，大根堆//        注意，建完堆之后是局部有序的，建堆的复杂度是O（n）
//        从n/2-1开始的原因：下标为i的节点的父节点下标是(i-1)/2,当i=n-1时，代入得i=n/2-1for( int i = n/2-1;i>=0;i--){heapify(arr,n,i);}//        排序//每次取堆中最大元素并维护堆的性质for( int i=n-1;i>0;i--){int temp = arr[i];arr[i] = arr[0];arr[0] = temp;heapify(arr,i,0);}}
//        比较的具体过程public static void heapify(int[] arr,int n,int i){
//        父节点下标int largest = i;
//        左孩子下标int lson = 2 * i + 1;
//        右孩子下标int rson = 2 * i + 2;
//        比较父节点和左孩子，左孩子下标必须小于n，如果左孩子大，则替换父节点if(lson<n&&arr[largest]<arr[lson]){largest = lson;}
//        比较父节点和右孩子，右孩子下标必须小于n，如果右孩子大，则替换父节点if(rson<n&&arr[largest]<arr[rson]){largest = rson;}
//        如果不满足大根堆的性质，则进行交换
//        将父节点和左右孩子中较大的元素交换if(largest!=i){int temp = arr[largest];arr[largest] = arr[i];arr[i] = temp;
//            向下继续比较heapify(arr,n,largest);}}

归并排序

算法描述：采用递归与分治的思想，先把数组按照两两划分的原则对数组分割，直到每个分组都是一个元素，然后再按照之前分割的顺序比较大小之后进行两两合并。
时间复杂度：O(NlogN)
稳定性：稳定
代码：

public static void merge(int[] arr,int[] tempArr,int left,int mid,int right){
//        标记左半区第一个未排序的元素int l_pos = left;
//        标记右半区第一个未排序的元素int r_pos = mid + 1;
//        临时数组元素的下标int pos = left;
//        开始合并while (l_pos <= mid&&r_pos <= right){if(arr[l_pos] < arr[r_pos])tempArr[pos++] = arr[l_pos++];elsetempArr[pos++] = arr[r_pos++];}
//        可能左半区还有剩余元素while (l_pos <= mid)tempArr[pos++] = arr[l_pos++];
//        可能右半区还有剩余元素while (r_pos <= right)tempArr[pos++] = arr[r_pos++];
//        把临时数组的元素复制回主数组while (left <= right){arr[left] = tempArr[left];left++;}}public static void msort(int[] arr,int[] tempArr,int left,int right){
//        如果只有一个元素则不进行划分if(left < right){int mid = (left+right)/2;//递归划分左半部分msort(arr,tempArr,left,mid);//递归划分右半部分msort(arr,tempArr,mid+1,right);//合并merge(arr,tempArr,left,mid,right);}}public static void mergeSort(int[] arr){int n = arr.length;
//        分配一个辅助数组int[] tempArr = new int[n];
//        开始归并排序，传入左边界和右边界msort(arr,tempArr,0,n-1);}

整理也挺费时间的，如果觉得对你有帮助，点个赞再走吧！感谢收看！