排序汇总 java实现
排序比较
| 排序算法 | 平均时间复杂度 | 最差时间复杂度 | 空间复杂度 | 数据对象稳定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n2) | O(n2) | O(1) | 稳定 |
| 选择排序 | O(n2) | O(n2) | O(1) | 数组不稳定、链表稳定 |
| 插入排序 | O(n2) | O(n2) | O(1) | 稳定 |
| 快速排序 | O(n*log2n) | O(n2) | O(log2n) | 不稳定 |
| 堆排序 | O(n*log2n) | O(n*log2n) | O(1) | 不稳定 |
| 归并排序 | O(n*log2n) | O(n*log2n) | O(n) | 稳定 |
| 希尔排序 | O(n*log2n) | O(n2) | O(1) | 不稳定 |
| 计数排序 | O(n+m) | O(n+m) | O(n+m) | 稳定 |
| 桶排序 | O(n) | O(n) | O(m) | 稳定 |
| 基数排序 | O(k*n) | O(n2) | 稳定 |
冒泡排序
public void sort(int[] nums){
int n = nums.length;
if(n == 0) return ;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if(nums[j] > nums[j+1])
swap(nums, j, j+1);
}
}
}
private void swap(int[] nums, int i , int j){
int tmp = nums[i];
nums[i] = nums[ j];
nums[j] = tmp;
}选择排序
注意： 第二层循环用来找最小值索引
public void sort(int[] nums){
int n = nums.length;
if(n == 0) return;
for(int i = 0; i < n; i++){
int min = i;
for(int j = i; j < n; j++){
if(nums[j] < nums[min])
min = j;
}
swap(nums, i, min);
}
}
private void swap(int[] nums, int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}插入排序
细节：第二次循环是 j--
public void sort(int[] nums){
int n = nums.length;
if(n == 0) return ;
for (int i = 1; i < n; i++) {
for (int j = i; j > 0 && nums[j] < nums[j-1]; j--) {
swap(nums, j, j-1);
}
}
}
private void swap(int[] nums , int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}快速排序
细节：在partition函数中，里面的while必须要有，先判断 i 和 j 是否越界，最后出口，搞一个已经拍好序的数组来思考下
public void sort(int[] nums){
int n = nums.length;
if(n == 0) return;
quickSort(nums, 0, n-1);
}
private void quickSort(int[] nums, int lo, int hi){
if(lo >= hi) return;
int mid = patition(nums, lo, hi);
quickSort(nums, lo, mid-1);
quickSort(nums, mid+1, hi);
}
private int patition(int[] nums, int lo, int hi){
int i = lo;
int j = hi+1;
while (i < j){
while (++i <= hi && nums[i] < nums[lo]);
while (--j >= lo && nums[j] > nums[lo]);
if(i < j)
swap(nums, i, j);
}
swap(nums, lo, j);
return j;
}
private void swap(int[] nums, int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}堆排序
先建立堆，堆从一半位置开始建立就可以了
细节点：开始的n是长度-1；在下沉时如果比两边都大，就退出了
public void sort(int[] nums){
int n = nums.length-1;
//建堆
for (int k = (n-1)/2; k >= 0; k--) {
sink(nums, k, n);
}
//排序
while (n > 0){
swap(nums, 0, n--);
sink(nums, 0, n);
}
}
private void sink(int[] nums, int k, int n){
while (2*k + 1 <= n){
int j = 2*k+1;
if(j < n && nums[j] < nums[j+1]) j++;
if(nums[j] < nums[k]) break;
swap(nums, j, k);
k = j;
}
}
private void swap(int[] nums, int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}归并排序
细节：注意merge时判断大小是用aux，否则会出错
public void sort(int[] nums){
int n = nums.length;
if(n == 0) return;
aux = new int[n];
mergeSort(nums, 0 , n-1);
}
int[] aux;
private void mergeSort(int[] nums, int lo ,int hi){
if(lo >= hi) return;
int mid = lo + (hi - lo)/2;
mergeSort(nums, lo, mid);
mergeSort(nums,mid+1,hi);
if(nums[mid] >nums[mid+1])
merge(nums, lo, mid, hi);
}
private void merge(int[] nums, int lo, int mid, int hi){
for(int k = lo; k <= hi; k++)
aux[k] = nums[k];
int i = lo;
int j = mid+1;
for (int k = lo; k <= hi; k++) {
if(i > mid) nums[k] = aux[j++];
else if(j > hi) nums[k] = aux[i++];
else if(aux[i] > aux[j]){
nums[k] = aux[j++];
}else{
nums[k] = aux[i++];
}
}
}希尔排序
注意：先得到h为多少，然后第一层循环从h开始，第二层循环判断条件时 >= h; 且都是 - h
public void sort(int[] nums){
int n = nums.length;
int h = 1;
while (h < n/3) h = h*3+1;
while (h >= 1){
for (int i = h; i < n; i++) {
for (int j = i; j >= h && nums[j] < nums[j-h]; j-=h) {
swap(nums,j, j-h);
}
}
h = h/3;
}
}
private void swap(int[] nums, int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}计数排序
记录一个最小最大值，从而减少桶的数量
private void sort(int[] nums){
int n = nums.length;
if(n == 0) return;
int min = nums[0];
int max = nums[0];
for(int num : nums){
min = Math.min(min, num);
max = Math.max(max, num);
}
int[] bucket = new int[max-min+1];
for (int i = 0; i < nums.length; i++) {
bucket[nums[i]-min]++;
}
int idx = 0;
for (int i = min; i <= max; i++) {
for (int j = 0; j < bucket[i]; j++) {
nums[idx++] = i;
}
}
}桶排序
range多大，就需要多大的桶
private void sort(int[] nums, int range){
int[] bucket = new int[range];
for (int i = 0; i < nums.length; i++) {
bucket[nums[i]]++;
}
int idx = 0;
for (int i = 0; i < range; i++) {
for (int j = 0; j < bucket[i]; j++) {
nums[idx++] = i;
}
}
}基数排序
public void sort(int[] nums){
int n = nums.length;
if(n == 0) return;
int[] aux = new int[n];
int max = nums[0];
for(int num : nums)
max = Math.max(max, num);
for(int base = 1; max / base > 0; base*=10){
int[] count = new int[11]; //这里写为11很关键
//统计频率
for (int i = 0; i < n; i++)
count[(nums[i] / base) % 10 + 1]++; //这里从1开始很关键
//将频率转换为索引
for(int i = 1; i < count.length; i++)
count[i] += count[i-1];
//将元素分类
for(int i = 0; i < n; i++)
aux[count[(nums[i] / base) % 10]++] = nums[i]; //这里++很关键
//回写
for(int i = 0; i < n; i++)
nums[i] = aux[i];
}
}