八大基础排序
冒泡排序
对相邻的元素，不断进行比较，就像小泡泡一样，向上浮动。
for(int i = 0; i < n; i++)
for(int j = i + 1; j < n; j ++)
if(a[i] > a[j]){// swap
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
冒泡的一个小优化：
for(int i = 0; i < n; i++){
boolean flag = true;
for(int j = i + 1; j < n; j ++){
if(a[i] > a[j]){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
flag = false;
}
}
if(flag)break;// 如果此轮都没有交换，则代表已排好序，退出。
}
插入排序
将数组分为两个部分，一部分是排好序的，一部分是未排好序的，从未排序中选一个元素，插入到排序的部分，插入后依然有序。
// 两个for
for (int i = 1; i < n; i++) {
int cur = a[i],j;
for(j = i - 1; j >= 0 && a[j] > cur; j --)a[j + 1] = a[j];// 先往后挪，然后再插入
a[j + 1] = cur;
}
// for + while
for (int i = 1; i < n; i++) {
int cur = a[i],j = i - 1;
while(j >= 0 && a[j] > cur){
a[j + 1] = a[j];
j--;
}
a[j + 1] = cur;
}
选择排序
找到最小的元素插在第0位置，找到第二小的元素插在第1位置，以此类推；
for (int i = 0; i < n; i++) {
int minIndex = i;
for(int j = i + 1; j < n; j++){
if(a[j] < a[minIndex])minIndex = j; // 寻找最小值的下标
}
// swap()
int temp = a[i];
a[i] = a[minIndex];
a[minIndex] = temp;
}
快速排序
快排思路：选择一个基数，每次遍历将大于基数的数放在右边，小于的放在左边，然后对此基数的左右两边做重复的操作。
时间复杂度分析：每次从i==j处分开，分开期望值为（1/2）故平均时间复杂度为O(nlogn)，若每次都在 I=j =left或者i=j=right（两边分开）相当于双重循环，最差时间复杂度O(n^2)；最优就是每次都在中间分开，复杂度为O(nlogn);
//yxc模板：
public static void quickSort(int[] q, int l, int r){
if(l >= r) return ;
int x = q[l + r >> 1];
int i = l - 1, j = r + 1; //正是先变换坐标，再进行判断，故i = l - 1, j = r + 1
while(i < j){
do i++; while(q[i] < x);//每次都先进行坐标变换，导致最后i==j+1
do j--; while(q[j] > x);//两个wehile判断均没有=号，会在一开始就移动基准数。正是由于第一次便移动的基数，故
if(i < j){
int t = q[i];
q[i] = q[j];
q[j] = t;
}
}// i == j + 1;
quickSort(q,l,j);
quickSort(q,j + 1,r);
}
此快排注意点：当基数选择在左边时，必须是右哨兵先动，因为右哨兵停下时，一定是小于基数的数，这样能保证
//交换基数时
a[left] = a[l];
a[l] = temp;
不会将大于基数的数，与left交换。
当基数选择在最右边同理，要先动左哨兵。
public static void quickSort(int left, int right, int[] a){
if(left >= right)return ;
int temp = a[left];
int l = left, r = right;
while(l < r){
while(l < r && a[r] > temp) r--;
while(l < r && a[l] <= temp) l++;//必须要有这个=号的判断，因为此模板是先判断后再进行坐标的变化，不同于上面的模板。只有这样才能保证最终i==j 否则当有两个数相等时，无法跳出循环，会陷入死循环。正式由于此处的=号判断，导致其最后要将基数调换，因为基数在最初时，不会进行调换。
if(l < r){
int t = a[r];
a[r] = a[l];
a[l] = t;
}
}//出来时，保证了i==j，并且基数会是最终的位置。
a[left] = a[l];
a[l] = temp;
quickSort(left,l-1,a);//由于基数是最终位置，故只需递归两边
quickSort(l+1,right,a);
}
归并排序
不断划分子数组，永远划分成一半，这样必定需要划分logN每次遍历n次，故时间复杂度为O(nlogn)，且最优，最差，平均复杂度都是O(nlogn)。
private static void merge_sort(int[] q, int l, int r) {
// 递归出调节
if(l >= r)return ;
//不断二分
int mid = l + r >> 1;
//递归子区间
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);
int i = l, j = mid + 1, k = 0;
// 此时分成左边数组和右边数组并且都是升序的，利用双指针将左右按升序放入额外开辟的数组temp中
while(i <= mid && j <= r) {
if(q[i] <= q[j])temp[k++] = q[i++];
else temp[k++] = q[j++];
}
// 右边数组放完， 左边还有剩
while(i <= mid)temp[k++] = q[i++];
// 左边数组放完， 右边还有剩
while(j <= r)temp[k++] = q[j++];
//将临时数组，放入原数组中
for(i = l,k = 0; i <= r;)q[i++] = temp[k++];
}
堆排序
堆：分为大顶堆和小顶堆;
-
大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
-
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
import java.util.Scanner;
public class Main {
static Scanner sc = new Scanner(System.in);
static int size = 0;
static final int N = 100050;
public static void main(String[] args) {
int n = sc.nextInt();
int[] heap = new int[N];
for(int i = 1; i <= n;i ++){
int u = sc.nextInt();
insert(heap,u);
}
// 排序，将 最大的 放最后面 （大顶堆）
for(int i = 1; i <= n; i ++){
swap(heap,1,size);
size --;
push_down(heap,1);
}
for(int i = 1; i <= n; i ++) System.out.print(heap[i] + " ");
}
// 大顶堆 向上传
private static void push_down(int[] heap,int u){
int t = u, l_son = u * 2, r_son = u * 2 + 1;
while(l_son <= size && heap[l_son] > heap[t])t = l_son;
while(r_son <= size && heap[r_son] > heap[t])t = r_son;
if(t != u){
swap(heap,t,u);
push_down(heap,t);
}
}
private static void push_up(int[] heap, int u){
while(u / 2 > 0 && heap[u / 2] < heap[u]){
swap(heap,u / 2, u);
u /= 2;
}
}
private static void insert(int[] heap,int v){
heap[++ size] = v;
push_up(heap,size);
}
private static void remove_top(int[] heap){
heap[1] = heap[size--];
push_down(heap,1);
}
private static void swap(int[] a, int i, int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
基数排序
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
static Scanner sc = new Scanner(System.in);
public static void main(String[] args) {
// digit 代表最大值有多少位
int n = sc.nextInt(), max = Integer.MIN_VALUE,digit = 0;
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
max = Math.max(max,a[i]);
}
while(max > 0){
max /= 10;
digit ++;
}
// 基数排序
radix_sort(a,digit);
for (int i = 0; i < n; i++) System.out.print(a[i] + " ");
}
/**
* 从低位往高位依次排序，将所有位数的排序结果都排过后即为答案
* @param a
* @param digit
*/
private static void radix_sort(int[] a,int digit){
// cnt[0] 存在 第i位 位0 的所有数，
ArrayList[] cnt = new ArrayList[10];
for(int i = 0; i < 10; i ++)cnt[i] = new ArrayList<Integer>();
for(int i = 0; i < digit; i ++){
// 对下一位进行排序，比如 十位，则cnt里面存的是个位的排序结果，将其清空
for(int j = 0; j < 10; j ++)cnt[j].clear();
// 将其 按 位数 放入桶中
for(int j = 0; j < a.length; j ++){
cnt[get(a[j],i)].add(a[j]);
}
// 取出来，赋值给 原数组
for(int j = 0, k = 0; j < 10; j ++){
for(Object x : cnt[j]){
Integer t = (Integer)x;
a[k ++] = t;
}
}
}
}
private static int get(int i, int i1) {
while(i1-- > 0)i /= 10;
return i % 10;
}
}
希尔排序
略：
若我的讲得不够详细，可以去https://sort.hust.cc/10.radixsort；
参考学习：https://sort.hust.cc/10.radixsort + y总；
转载：https://blog.csdn.net/foolishpichao/article/details/105903992
查看评论