十大排序算法
2021-03-31 12:02:31 26 举报AI智能生成
请大家不要直接克隆，着手梳理一遍才会变成自己的知识
作者其他创作
大纲/内容
选择排序
时间复杂度
O(N²)
空间复杂度
O(1)
稳定性
不稳定
7 5 10 10 2 4 2
7 5 10 2 2 4 10
代码实现
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;
}
}
冒泡排序
时间复杂度
最坏---逆序
O(N²)
最好---完全有序
O(N)
空间复杂度
O(1)
稳定性
稳定
代码实现
基础版
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;
}
}
}
}
本身就是升序
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;
}
}
尾部局部有序，减少比较次数
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;
}
}
插入排序
时间复杂度
O(N²)
空间复杂度
O(1)
稳定性
稳定
代码实现
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;
}
}
快速排序
时间复杂度
O(nlogn)
空间复杂度
O(logn)
稳定性
稳定
代码实现
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);
}
归并排序
时间复杂度
O(nlogn)
空间复杂度
O(N)
稳定性
稳定
代码实现
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++];
}
}
堆排序
时间复杂度
O(nlogn)
空间复杂度
O(1)
稳定性
不稳定
代码实现
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;
}
希尔排序
时间复杂度
O(N^1.3)
空间复杂度
O(1)
稳定性
不稳定
代码实现
基础版
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;
}
}
}
基于Knuth的序列，h = 3h +1
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;
}
}
}
桶排序
时间复杂度
O(n+k)
空间复杂度
O(n+k)
稳定性
根据桶内排序算法而定
代码实现
形式不固定
基数排序
时间复杂度
O(n*k)
空间复杂度
O(n*k)
稳定性
稳定
代码实现
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);
}
}
计数排序
时间复杂度
O(n+k)
空间复杂度
O(n+k)
稳定性
稳定
代码实现
不稳定
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];
}
}
改进成稳定
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];
}
}
0 条评论
下一页
