冒泡排序
时间复杂度 o(n²)
空间复杂度 o(1)
稳定
for(int i = 0; i < nums.length-1 ; i++){
for(int j = 0; j < nums.length-1-i; j++)
if (nums[j] > nums[j+1]){
int tmp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = tmp;
}
}
注意点：外层代表循环次数，内层每次循环需比对次数
循环次数 若有三个数 循环两次即可
比对次数 若有三个数 比对两次即可
插入排序
时间复杂度 o(n²)
空间复杂度 o(1)
稳定
for(int i = 0; i < n.length; i++){
for (int j = i; j > 0; j--){
if (n[j] > n[j-1]){
break;
}
int tmp = nums[j];
nums[j] = nums[j-1];
nums[j-1] = tmp;
}
}
选择排序
时间复杂度 o(n²)
空间复杂度 o(1)
不稳定
与冒泡相比减小交换次数
for(int i = 0; i < nums.length; i++){
int min_index = i
for (int j = i+1; j < nums.length; j++){
if (nums[j] < nums[min_index])
min_index = j;
}
int tmp = nums[i];
nums[i] = nums[min_index];
nums[min_index] = tmp;
}
希尔排序
时间复杂度 o(n1.3) 最坏o(n²)
空间复杂度 o(1)
稳定 //4个循环 吓人
for (int gap = nums.length / 2; gap > 0; gap /= 2) {
//第一步确定间距
//第二步一个 gap 里面有多少个值 需要gap次
for (int i = 0; i < gap; i++) {
//第三步进行比对
for (int j = i + gap; j < nums.length; j += gap) {
if (nums[j] < nums[j - gap]) {
int tmp = nums[j];
int k = j - gap;
//进行迭代
while (k >= 0 && nums[k] > tmp) {
nums[k + gap] = nums[k];
k -= gap;
}
nums[k + gap] = tmp;
}
}
}
}
归并排序
时间复杂度 o(nlog2n)
空间复杂度 o(n)
稳定 合并链表
递归实现
public class MergeSort {
//两路归并算法，两个排好序的子序列合并为一个子序列
public void merge(int []a,int left,int mid,int right){
int []tmp=new int[a.length];//辅助数组
int p1=left,p2=mid+1,k=left;//p1、p2是检测指针，k是存放指针
while(p1<=mid && p2<=right){
if(a[p1]<=a[p2])
tmp[k++]=a[p1++];
else
tmp[k++]=a[p2++];
}
while(p1<=mid) tmp[k++]=a[p1++];//如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
while(p2<=right) tmp[k++]=a[p2++];//同上
//复制回原素组
for (int i = left; i <=right; i++)
a[i]=tmp[i];
}
public void mergeSort(int [] a,int start,int end){
if(start<end){//当子序列中只有一个元素时结束递归
int mid=(start+end)/2;//划分子序列
mergeSort(a, start, mid);//对左侧子序列进行递归排序
mergeSort(a, mid+1, end);//对右侧子序列进行递归排序
merge(a, start, mid, end);//合并
}
}
}
堆排序
直接构造堆
时间复杂度 o(nlog2n)
空间复杂度 o(1)
先构建一个大顶堆/(构建小顶堆不能保证顺序)
public static void sort(int[] nums){
//创建堆
for (int i = (nums.length - 1) / 2; i >= 0; i--) {
//从第一个非叶子结点从下至上，从右至左调整结构
//为什么输入这个呢？
adjustHeap(nums, i, nums.length);
}
//调整堆结构+交换堆顶元素与末尾元素
for (int i = nums.length - 1; i > 0; i--) {
//将堆顶元素与末尾元素进行交换
swap(0,i);
//重新对堆进行调整
adjustHeap(nums, 0, i);
}
}
private static void adjustHeap(int[] nums, int parent, int length) {
//将temp作为父节点
int tmp = nums[parent];
for(int k = i*2+1; k<length;k=k*2+1){
//若右节点存在 取左右节点大的那个
if (k+1 < length && nums[k]<nums[k+1]){
k++;
}
//进行比对
if (nums[k] > tmp){
nums[parent] = nums[k];
parent = k;
} else {
break;
}
}
nums[parent] = tmp;
}
快速排序
时间复杂度 o(nlog2n)
空间复杂度 o(1)
不稳定
分治算法
public static void quickSort(int[] nums, int low, int high){
if (low < high){
int privotLoc = partition(nums, low, high);
quickSort(nums, low, privotLoc - 1);
quickSort(nums, privotLoc + 1, high);//会出-1
}
}
public static int partition(int[] nums, int low, int high){
int privotKey = nums[low];
int begin = low;
while (low < high){
while(low < high && nums[high] >= privotKey)
--high;
while(low < high && nums[low] <= privotKey)
++low;
if (low < high){
swap(nums, low, high);
}
}
swap(nums, begin, low);
return low;
}
private static void swap(int[] nums, int low, int high) {
int tmp = nums[low];
nums[low] = nums[high];
nums[high] = tmp;
}
基数排序
//arr是要排序的数组，max是数组中最大的数有几位
public static void lsd_RadixSort(int[] arr,int max)
{
//count数组用来计数
int[] count = new int[10];
//bucket用来当桶（在下面你就理解了什么是桶了），放数据，取数据
int[] bucket = new int[arr.length];
//k表示第几位，1代表个位，2代表十位，3代表百位
for(int k=1;k<=max;k++)
{
//把count置空，防止上次循环的数据影响
for(int i=0;i<10;i++)
{
count[i] = 0;
}
//分别统计第k位是0,1,2,3,4,5,6,7,8,9的数量
//以下便称为桶
//即此循环用来统计每个桶中的数据的数量
for(int i=0;i<arr.length;i++)
{
count[getFigure(arr[i],k)]++;
}
//利用count[i]来确定放置数据的位置
for(int i=1;i<arr.10;i++)
{
count[i] = count[i] + count[i-1];
}
//执行完此循环之后的count[i]就是第i个桶右边界的位置
//利用循环把数据装入各个桶中，注意是从后往前装
//这里是重点，一定要仔细理解
for(int i=arr.length-1;i>=0;i--)
{
int j = getFigure(arr[i],k);
bucket[count[j]-1] = arr[i];
count[j]--;
}
//将桶中的数据取出来，赋值给arr
for(int i=0,j=0;i<arr.length;i++,j++)
{
arr[i] = bucket[j];
}
}
}
//此函数返回整型数i的第k位是什么
public static int getFigure(int i,int k)
{
int[] a = {1,10,100};
return (i/a[k-1])%10;
}
