首页  思维导图  详情

十大排序算法

2021-03-31 12:02:31   28  举报





AI智能生成

请大家不要直接克隆，着手梳理一遍才会变成自己的知识

排序算法

作者其他创作

大纲/内容

选择排序

时间复杂度

O(N²)

空间复杂度

O(1)

稳定性

不稳定

7   5   10   10   2   4   2

7   5   10   2   2   4   10

代码实现

<pre style="background-color: rgb(43, 43, 43); font-family: "JetBrains Mono", monospace; font-size: 9.8pt; color: rgb(169, 183, 198);">public static void sort(int[] nums){ for (int end = nums.length - 1; end > 0; end--) { int maxIndex = 0; //start <= end有助于解决一定的不稳定性，但不是完全解决 for(int start = 1; start <= end ;start++){ if(nums[start] >= nums[maxIndex]){ maxIndex = start; } } int temp = nums[maxIndex]; nums[maxIndex] = nums[end]; nums[end] = temp; } } </pre>

冒泡排序

时间复杂度

最坏---逆序

O(N²)

最好---完全有序

O(N)

空间复杂度

O(1)

稳定性

稳定

代码实现

基础版

<pre style="background-color: rgb(43, 43, 43); font-family: "JetBrains Mono", monospace; font-size: 9.8pt; color: rgb(169, 183, 198);"> public static void sort(int[] nums){ for (int end = nums.length - 1; end > 0; end--) { for(int start = 0; start < end ;start++){ if(nums[start] > nums[start+1]){ int temp = nums[start+1]; nums[start+1] = nums[start]; nums[start] = temp; } } } } </pre>

本身就是升序

<pre style="background-color: rgb(43, 43, 43); font-family: "JetBrains Mono", monospace; font-size: 9.8pt; color: rgb(169, 183, 198);"> public static void sort(int[] nums){ for (int end = nums.length - 1; end > 0; end--) { //判断是否本身就有序的标志 boolean sorted = true; for(int start = 0; start < end ;start++){ if(nums[start] > nums[start+1]){ int temp = nums[start+1]; nums[start+1] = nums[start]; nums[start] = temp; //一旦出现一次交换，则无序 sorted = false; } } //如果没有重排，则数组有序 if(sorted)break; } } </pre>

尾部局部有序，减少比较次数

<pre style="background-color: rgb(43, 43, 43); font-family: "JetBrains Mono", monospace; font-size: 9.8pt; color: rgb(169, 183, 198);"> public static void sort(int[] nums){ for (int end = nums.length - 1; end > 0; end--) { //判断是否本身就有序的标志 boolean sorted = true; //如果last=end，数组完全有序，last则不会变化，就会退回基础版 int last = 1; for(int start = 0; start < end ;start++){ if(nums[start] > nums[start+1]){ int temp = nums[start+1]; nums[start+1] = nums[start]; nums[start] = temp; last = start + 1; //一旦出现一次交换，则无序 sorted = false; } } end = last; //如果没有重排，则数组有序 if(sorted)break; } } </pre>

插入排序

时间复杂度

O(N²)

空间复杂度

O(1)

稳定性

稳定

代码实现

<pre style="background-color: rgb(43, 43, 43); font-family: "JetBrains Mono", monospace; font-size: 9.8pt; color: rgb(169, 183, 198);"> public static void sort(int[] arr){ for (int i = 1; i < arr.length; i++) { int temp = arr[i]; int j = i; while(j > 0 && temp < arr[j - 1]){ arr[j] = arr[j - 1]; j--; } arr[j] = temp; } } </pre>

快速排序

时间复杂度

O(nlogn)

空间复杂度

O(logn)

稳定性

稳定

代码实现

<pre style="background-color: rgb(43, 43, 43); font-family: "JetBrains Mono", monospace; font-size: 9.8pt; color: rgb(169, 183, 198);">public static void sort(int[] arr,int left,int right){ if(left >= right)return; int i = left, j = right; //取第一个数作为基数 int temp = arr[left]; while(i < j){ //先从右往左找，填第一个坑 while (i < j && arr[j] > temp)j--; if(i < j)arr[i++] = arr[j]; while (i < j && arr[i] < temp)i++; if(i < j)arr[j--] = arr[i]; } arr[i] = temp; sort(arr,left,i-1); sort(arr,i+1,right); } </pre>

归并排序

时间复杂度

O(nlogn)

空间复杂度

O(N)

稳定性

稳定

代码实现

<pre style="background-color: rgb(43, 43, 43); font-family: "JetBrains Mono", monospace; font-size: 9.8pt; color: rgb(169, 183, 198);"> public static void sort(int[] arr,int left,int right){ if (left >= right)return; int mid = left + (right - left) / 2; sort(arr,left,mid); sort(arr,mid+1,right); merge(arr,left,mid+1,right); } public static void merge(int[] arr,int left,int mid,int right){ int[] temp = new int[right - left + 1]; int index = 0; int i = left; int j = mid; while(i < mid && j <= right){ if(arr[i] < arr[j]){ temp[index++] = arr[i++]; }else{ temp[index++] = arr[j++]; } } while (i < mid){ temp[index++] = arr[i++]; } while (j <= right){ temp[index++] = arr[j++]; } index = 0; for (int k = left; k <= right; k++) { arr[k] = temp[index++]; } } </pre>

堆排序

时间复杂度

O(nlogn)

空间复杂度

O(1)

稳定性

不稳定

代码实现

<pre style="background-color: rgb(43, 43, 43); font-family: "JetBrains Mono", monospace; font-size: 9.8pt; color: rgb(169, 183, 198);"> public static void sort(int[] arr){ int len = arr.length; //构建大顶堆 for (int i = (len - 1 ) / 2; i >= 0; i--) { heapify(arr, i, len); } for (int i = len - 1; i >= 0 ; i--) { System.out.println(arr[0]); swap(arr,i,0); heapify(arr,0,i); } } public static void heapify(int arr[],int now,int len){ int left = 2 * now + 1; int right = 2 * now + 2; int maxIndex = now; if(left < len && arr[left] > arr[maxIndex]){ maxIndex = left; } if(right < len && arr[right] > arr[maxIndex]){ maxIndex = right; } if(maxIndex != now){ swap(arr,maxIndex,now); heapify(arr,maxIndex,len); } } public static void swap(int[] arr, int i, int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } </pre>

希尔排序

时间复杂度

O(N^1.3)

空间复杂度

O(1)

稳定性

不稳定

代码实现

基础版

<pre style="background-color: rgb(43, 43, 43); font-family: "JetBrains Mono", monospace; font-size: 9.8pt; color: rgb(169, 183, 198);"> public static void sort(int[] arr){ //gap是空格间隙 for(int gap = 4; gap > 0; gap/=2){ //内部还是插入排序 for (int i = gap; i < arr.length; i++) { int j = i; int temp = arr[j]; while(j > gap - 1 && temp < arr[j-gap]){ arr[j] = arr[j-gap]; j -= gap; } arr[j] = temp; } } } </pre>

基于Knuth的序列，h = 3h +1

<pre style="background-color: rgb(43, 43, 43); font-family: "JetBrains Mono", monospace; font-size: 9.8pt; color: rgb(169, 183, 198);">public static void sort(int[] arr){ int h = 1; while(h <= arr.length/3){ h = h*3 + 1; } for(int gap = h; gap > 0; gap = (gap-1)/3){ //内部还是插入排序 for (int i = gap; i < arr.length; i++) { int j = i; int temp = arr[j]; while(j > gap - 1 && temp < arr[j-gap]){ arr[j] = arr[j-gap]; j -= gap; } arr[j] = temp; } } } </pre>

桶排序

时间复杂度

O(n+k)

空间复杂度

O(n+k)

稳定性

根据桶内排序算法而定

代码实现

形式不固定

基数排序

时间复杂度

O(n*k)

空间复杂度

O(n*k)

稳定性

稳定

代码实现

<pre style="background-color: rgb(43, 43, 43); font-family: "JetBrains Mono", monospace; font-size: 9.8pt; color: rgb(169, 183, 198);">public static void sort(int[] arr){ //求最高位数 int max = 0; int min = 0; for (int i : arr) { if (i > max)max = i; if (i < min)min = i; } int digit = 1; while(max / 10 > 0){ max /= 10; digit++; } //开始基数排序 for (int i = 1; i <= digit; i++) { int[] count = new int[10]; int[] result = new int[arr.length]; //求每次该和多少取余 int times = 1; for(int j = 1;j < i; j++){ times *= 10; } for (int k = 0; k < arr.length; k++) { count[(arr[k]/times)%10]++; } for (int l = 1; l < count.length; l++) { count[l] += count[l-1]; } for (int m = arr.length - 1; m >= 0 ; m--) { result[--count[(arr[m]/times)%10]] = arr[m]; } System.arraycopy(result,0,arr,0,arr.length); } } </pre>

计数排序

时间复杂度

O(n+k)

空间复杂度

O(n+k)

稳定性

稳定

代码实现

不稳定

<pre style="background-color: rgb(43, 43, 43); font-family: "JetBrains Mono", monospace; font-size: 9.8pt; color: rgb(169, 183, 198);">public static void sort(int[] arr,int low,int high){ int[] count = new int[high - low + 1]; int[] result = new int[arr.length]; for (int i : arr) { count[i]++; } for (int i = 0; i < result.length; i++) { for (int j = 0; j < count.length; j++) { while (count[j]-- > 0){ result[i++] = j; } } } for (int i = 0; i < arr.length; i++) { arr[i] = result[i]; } } </pre>

改进成稳定

<pre style="background-color: rgb(43, 43, 43); font-family: "JetBrains Mono", monospace; font-size: 9.8pt; color: rgb(169, 183, 198);">public static void sort(int[] arr,int low,int high){ int[] count = new int[high - low + 1]; int[] result = new int[arr.length]; for (int i : arr) { count[i - low]++; } for (int i = 1; i < count.length; i++) { count[i] = count[i] + count[i-1]; } for (int i = arr.length - 1; i >= 0; i--) { result[--count[arr[i] - low]] = arr[i]; } for (int i = 0; i < arr.length; i++) { arr[i] = result[i]; } } </pre>