常用的排序算法

曾经终败给现在 2023-02-24 15:26 2阅读 0赞

1.冒泡排序  
从第一个数开始，每一个和右边相邻的比较，如果比右边的大，和右边的交换，最终结果是最大的“冒泡”到最右边。右边渐渐有序，向左延伸。  
时间复杂度O(n^2)

public static void sort(int[] nums) { 
    	boolean hasChange = true;
    	for (int i=0; i<nums.length-1 && hasChange; i++) { 
    		hasChange = false;
    		for (int j=0; j<nums.length-1-i; j++) { 
    			if (nums[j] > nums[j+1]) { 
    				int temp = nums[j+1];
    				nums[j+1] = nums[j];
    				nums[j] = temp;
    				hasChange = true;
    			} 
    		}
    	}
    }

2.插入排序  
左边的是排好序的，从待排序的第一个数开始找到左边比它小的数放到其后面。  
时间复杂度O(n^2)

public static void sort(int[] nums) { 
    	for (int i=1, j, curr; i<nums.length; i++) { 
    		curr = nums[i];
    		for (int j=i-1; j>=0; j--) { 
    			if (nums[j] > curr) { 
    				nums[j+1] = nums[j];
    			}
    		}
    		nums[j+1] = curr;
    	}
    }

3.归并排序  
不断地将数组二分，将两部分分别排序，再合并  
时间复杂度O(nlogn)

public static void sort(int[] nums, int lo, int hi) { 
    	if (lo >= hi) return;
    	int mid = lo + (hi-lo)/2;
    	sort(nums, lo, mid);
    	sort(nums, mid+1, hi);
    	merge(nums, lo, mid, hi);
    }
    
    public static void merge(int[] nums, int lo, int mid, int hi) { 
    	int[] copy = nums.clone();
    	int k=lo, i=lo, j=mid+1;
    
    	while (k <=hi) { 
    		if (i>mid) { 
    			nums[k++] = copy[j++];
    		} else if (j > hi) { 
    			nums[k++] = copy[i++];
    		} else if (copy[i] > copy[j]) { 
    			nums[k++] = copy[j++];
    		} else { 
    			nums[k++] = copy[i++];
    		}
    	}
    }

4.快速排序  
每次选择一个基准，将数组分为比基准大的和比基准小的两部分，基准所在位置就是其最终位置。  
时间复杂度O(nlogn)

public static void sort(int[] nums, int lo, int hi) { 
    	if (lo >= hi) return;
    	int p = partition(nums, lo, hi);
    	sort(nums, lo, p-1);
    	sort(nums, p+1; hi);
    }
    
    public static int partition(int[] nums, int lo, int hi) { 
    	swap(nums, randRange(lo, hi), hi);
    	int i,j;
    	for (l=lo, j=lo; j<hi; j++) { 
    		if (nums[j] <= nums[hi]) { 
    			swap(nums, i++, j);
    		}
    	}
    	swap(nums, i, hi);
    	return i;
    }
    
    public static void swap(int[] nums, int i, int j) { 
    	if (i==j) return;
    	int tmp = nums[i];
    	nums[i] = nums[j];
    	nums[j] = tmp;
    }

5.拓扑排序  
对有向无环图进行拓扑排序，将入度为0的顶点放入队列中，每次出队一个，并将其指向的顶点的入度减一，如果其入度为0，放入队列，直到队列为空，看排序的顶点个数和图的顶点个数是否相等，相等则排好序。