- 1. 排序相关概念
- 2. 选择排序
- 2.1 直接选择排序
- 2.2 堆排序
- 3. 交换排序
- 3.1 冒泡排序
- 3.2 快速排序
- 4. 插入排序
- 4.1 直接插入排序
- 4.2 折半插入排序
- 4.3 希尔排序
- 5. 归并排序
- 6. 计数排序
- 7. 桶排序
- 8. 基数排序
排序算法的评价：
- 时间复杂度：主要分析关键字的比较次数和记录的移动次数
- 空间复杂度：需要的辅助内存的大小
- 稳定性：假设数据在有两个2，这两个2排序之后的相对顺序不变
外部排序：需要借助外部存储器，如磁盘（多路归并排序）
内部排序：仅需要内存
内部排序类：
- 选择排序：直接选择排序、堆排序
- 交换排序：冒泡排序、快速排序
- 插入排序：直接插入排序、折半插入排序、希尔排序
- 归并排序
- 线性排序算法：计数排序、桶排序、基数排序
特点：
- n个数据需要n-1趟比较
- 升序：每次选取当前未处理元素中的最小元素放在数组前面
- 降序：每次选取当前未处理元素中的最大元素放在数组前面
- 不稳定排序
- 时间复杂度: 最好 O ( n 2 ) O(n^2) quad O(n2)最坏 O ( n 2 ) O(n^2) quad O(n2)平均 O ( n 2 ) O(n^2) quad O(n2)
- 空间复杂度： O ( 1 ) O(1) O(1)
例子：对数据21 30 49 30* 16 9 加*号是为了判断排序之后数据是否稳定
package datastructure.sort;
import java.util.Arrays;
public class SelectSort {
public static void sort(int[] arr) {
int n=arr.length;
//依次进行n-1趟比较 第i趟选择第i小的值放在位置i上
for(int i=0;i
int minIndex=i;//假设当前最小数据就是arr[i]
for(int j=i+1;j//j=i+1: 第i个数据只和它后面的数据比较
if(arr[j]
minIndex=j;//minIndex保存本趟比较中较小值的索引
}
}
if(minIndex!=i) {//相等说明arr[i]就是当前最小 不用交换 不等需要交换
int tmp=arr[i];
arr[i]=arr[minIndex];
arr[minIndex]=tmp;
}
}
System.out.println(Arrays.toString(arr));
}
public static void main(String[] args) {
int[] arr= {21,30,49,30,16,9};
sort(arr);
}
}
2.2 堆排序
堆排序相关内容参考：优先队列和堆及相关问题
特点：
- 时间复杂度: 最好 O ( n l o g n ) O(nlogn) quad O(nlogn)最坏 O ( n l o g n ) O(nlogn) quad O(nlogn)平均 O ( n l o g n ) O(nlogn) quad O(nlogn)
- 空间复杂度：O(1）
- 不稳定排序
代码实现：
package datastructure.sort;
import java.util.Arrays;
public class HeapSort {
public static void sort(int arr[])
{
int N=arr.length;
//将数组元素构建出一个大顶堆
//最后一个节点编号是N-1 其父节点编号为:(N-1-1)/2=N/2-1
for(int k=N/2-1;k>=0;k--)// N/2-1指向最后一个父节点 从其开始调整
{
sink(arr,k,N);
}
//交换 下沉
while(N>0)
{
swap(arr, 0, N-1);
N--;//N--可以看出是删除堆顶最大元素 因此需要进行下沉操作进行调整
sink(arr, 0, N);//这里只需要sink一次是因为只影响了堆顶节点和其左右子节点的关系
}
System.out.println(Arrays.toString(arr));
}
public static void sink(int arr[],int k,int N)
{
while(2*k+1
int j=2*k+1;//指向左子节点
//根节点>=max(左子节点，右子节点)
if(j+1=arr[j])//找到<=根节点的子节点 停止
break;
swap(arr, k, j);
k=j;
}
}
public static void swap(int arr[],int i,int j)
{
int tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
public static void main(String[] args) {
int[] arr= {21,30,49,30,16,9};
sort(arr);
}
}
3. 交换排序
3.1 冒泡排序
特点：
- n个数据需要n-1趟比较
- 第1趟需要n-1次比较，最后一趟只需要1次比较，即越往后比较次数越少
- 每趟比较结束后，都能确定一个元素到数组的后面
- 如果某一趟没有进行交换，说明数组已经排好序了
- 稳定排序
- 时间复杂度：平均： O ( n 2 ) O(n^2) quad O(n2) 最坏： O ( n 2 ) O(n^2) quad O(n2) 最好： O ( n ) O(n) O(n) （使用了flag标志，如果数组本来就有序，第一趟比较后没有发生交换择排序结束）
- 空间复杂度：O(1)
例子：9 16 21* 23 30 49 21 30*
package datastructure.sort;
import java.util.Arrays;
public class BubbleSort {
public static void sort(int[] arr) {
int n=arr.length;
for(int pass=n-1;pass>=1;pass--) {//一共要n-1趟
boolean flag=false;
for(int i=0;i
if(arr[i]>arr[i+1]) {
int tmp=arr[i];
arr[i]=arr[i+1];
arr[i+1]=tmp;
flag=true;
}
}
if(!flag)//如果某趟没有发生交换 说明已经排好序
break;
}
System.out.println(Arrays.toString(arr));
}
public static void main(String[] args) {
int[] arr= {2,3,1,7,6,5,8,0,9,4};
sort(arr);
}
}
3.2 快速排序
特点：
- 一种分治的排序算法
- 将一个数组分成两个子数组，将两部分独立地排序
- 一个很重要的过程就是切分partition,切分过程总能排定一个元素，每次进行切分时，可以用子数组的第一个元素作为切分元素，切分完完成后，该切分元素左边的元素都不大于切分元素，切分元素右边的元素都不小于切分元素（以升序为例）
- 不稳定排序
- 时间复杂度：平均： O ( n l o g n ) O(nlogn) quad O(nlogn) 最好： O ( n l o g n ) O(nlogn) quad O(nlogn) 最坏： O ( n 2 ) O(n^2) O(n2) (最坏情况出现在每次切分的元素不能划分成两个子数组，比如数组有序，以第一个元素进行切分的话，实际上数组的规模并没有变小，为了解决这种情况，一般可以选随机选取一个元素，将该元素移动到数组首部或尾部作为切分元素，每次切分时都选取当前子数组中随机的一个元素)
- 空间复杂度： O ( n l o g n ) O(nlogn) quad O(nlogn) 最坏： O ( n ) O(n) quad O(n) 递归的栈空间
package datastructure.sort;
import java.util.Arrays;
public class QuickSort {
public static void quickSort(int arr[],int lo,int hi)
{
if(hi<=lo)
return;
int j=partition(arr,lo,hi);//j左边的元素不大于a[j],j右边的元素不小于a[j]
quickSort(arr,lo,j-1);
quickSort(arr,j+1,hi);
}
public static int partition(int arr[],int lo,int hi)
{
int i=lo;
int j=hi+1;
int v=arr[lo];//切分的元素
while (true)
{
//保证切分元素左边的元素都比它小，右边的元素都比它大
while (arr[++i]v)//查找比切分元素小的元素b
if(j==lo)
break;
if(i>=j)//左右扫描指针相等或左指针跑到右指针前面，说明扫描结束
break;
swap(arr,i,j);//交换前面找到的a b
}
swap(arr,lo,j);//最后交换切分元素，将切分元素放到指定的位置
return j;
}
public static void swap(int arr[],int i,int j)
{
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
public static void main(String[] args) {
int[] arr= {2,3,1,7,6,5,8,0,9,4};
quickSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
}
}
当然你可以使用最后一个元素作为切分元素，将上面的 partition方法修改如下即可：
public static int partition(int arr[],int lo,int hi)
{
int i=lo-1;
int j=hi;
int v=arr[hi];//切分的元素
while (true)
{
//保证切分元素左边的元素都比它小，右边的元素都比它大
while (arr[++i]v)//查找比切分元素小的元素b
if(j==lo)
break;
if(i>=j)//左右扫描指针相等或左指针跑到右指针前面，说明扫描结束
break;
swap(arr,i,j);//交换前面找到的a b
}
swap(arr,hi,i);//最后交换切分元素，将切分元素放到指定的位置
return i;
}
4. 插入排序
4.1 直接插入排序
思想：对于一个有序序列，从尾部再加入一个数字，使得这个序列依然有序
- n个数据需要n-1趟插入操作
- 每次插入完成保证数组开始到插入位置的区间内元素有序
- 时间复杂度： 平均： O ( n 2 ) O(n^2) quad O(n2) 最坏： O ( n 2 ) O(n^2) quad O(n2) 最好： O ( n ) O(n) O(n) （数组已经有序，每趟只需要比较1次就退出当前趟的比较）
- 空间复杂度：O(1）
- 稳定排序
package datastructure.sort;
import java.util.Arrays;
public class DirectInsertSort {
public static void sort(int[] arr) {
int n=arr.length;
//i=0 j=1 插入第2个元素
//i=1 j=2 插入第3个元素
//i=n-2 j=n-1 插入最后一个元素
//第i趟插入，将第i个元素插入到区间[0,i-1]元素序列中
for(int i=1;i<=n-1;i++) {
for(int j=i;j>0;j--) {
if(arr[j]//后面的小于前面的
int tmp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=tmp;
}else {//否则说明已经前面这部分有序了
break;
}
}
}
}
public static void main(String[] args) {
int[] arr= {21,30,49,30,16,9};
sort(arr);
System.out.println(Arrays.toString(arr));
}
}
4.2 折半插入排序
折半插入排序是对直接插入排序的一种优化，当插入第i个元素时，区间[0,i-1]内的元素其实已经有序，就不需要一个一个地去找元素i应该插入的位置，可以利用二分查找
package datastructure.sort;
import java.util.Arrays;
public class BinaryInsertSort {
public static void sort(int[] arr) {
int n=arr.length;
//i=0 j=1 插入第2个元素
//i=1 j=2 插入第3个元素
//i=n-2 j=n-1 插入最后一个元素
//第i趟插入，将第i个元素插入到区间[0,i-1]元素序列中
for(int i=1;i<=n-1;i++) {
int left=0,right=i-1;
while(left<=right) {
int mid=left+(right-left)/2;
//待插入元素arr[i]大于中间元素 arr[i]在中间元素的右边
if(arr[i]>=arr[mid])//这里取大于等于 即使30 30这种情况 后面的30不会插入到前面 保证稳定性
left=mid+1;
else {//待插入元素arr[i]小于中间元素 arr[i]在中间元素的左边
right=mid-1;
}
}
int tmp=arr[i];
for(int j=i;j>left;j--) {//[left+1,i-1]元素后移
arr[j]=arr[j-1];
}
arr[left]=tmp;//待插入元素arr[i]的位置是left left的含义：比arr[i]小的元素个数
}
}
public static void main(String[] args) {
int[] arr= {21,30,18,49,30,16,9};
sort(arr);
System.out.println(Arrays.toString(arr));
}
}
4.3 希尔排序
希尔排序是堆直接插入排序的一种改进，加大了插入排序元素中的间隔，并在这些有间隔的元素间进行插入排序，从而使得数据项大跨度地移动
一个例子：9 -16 21* 23 -30 -49 21 30* 30
当步长h为4时：
9和30形成有序
-16和-49形成有序
21和21形成有序
30和23形成有序
30 2 -30 形成有序
package datastructure.sort;
import java.util.Arrays;
public class ShellSort {
public static void sort(int[] arr) {
int n=arr.length;
int h=1;
while(h
h=3*h+1;//1 4 13 40.....
}
while(h>=1) {
//将数组变为h有序 arr[i] arr[i+h] arr[i+2h]...有序
for(int i=h;i
System.out.println("i="+i);
for(int j=i;j>=h;j-=h) {
System.out.println("j:"+j+" j-h:"+(j-h));
if(arr[j]//后面的比前面小
int tmp=arr[j];
arr[j]=arr[j-h];
arr[j-h]=tmp;
}
else {
break;
}
}
}
System.out.println("---------------------------");
h/=3;
}
}
public static void main(String[] args) {
int[] arr= {9 ,-16 , 21, 23 ,-30 ,-49, 21 ,30, 30};
sort(arr);
System.out.println(Arrays.toString(arr));
}
}
为了形象地打印过程，去掉else语句块中的break:
打印如下：
- 两个关键步骤：划分和合并
- 需要用一个临时数组来保存合并两个有序序列后的新序列
- 时间复杂度: 最好 O ( n l o g n ) O(nlogn) quad O(nlogn)最坏 O ( n l o g n ) O(nlogn) quad O(nlogn)平均 O ( n l o g n ) O(nlogn) quad O(nlogn)
- 空间复杂度：最好： O ( l o g n ) O(logn) quad O(logn) 最坏： O ( n ) O(n) quad O(n)
- 合并部分，也就是merge部分，代码实现类似于将两个有序数组合并的代码，首先是合并只有1个元素的两个数组，然后合并有两个元素的有序数组，，合并有4个元素的有序数组…
- 稳定排序
package datastructure.sort;
import java.util.Arrays;
public class MergeSort {
public static void merge(int arr[],int temp[],int lo,int mid,int hi)
{
int i=lo;
int j=mid+1;
int t=0;
while (i<=mid&&j<=hi)
{
if(arr[i]
if(hi<=lo)
return;
int mid=(lo+hi)/2;
mergeSort(arr,temp,lo,mid);//对左半部分进行排序
mergeSort(arr,temp,mid+1,hi);//对右半部分进行排序
merge(arr,temp,lo,mid,hi);//开始合并左半部分和右半部分
}
public static void main(String[] args) {
int[] arr= {2,3,1,7,6,5,8,0,9,4};
int[] tmp=new int[arr.length];
mergeSort(arr, tmp,0, arr.length-1);
System.out.println(Arrays.toString(arr));
}
}
归并排序的详细解释：归并排序自顶向下和自底向上分析及实现
下面介绍的是线程时间复杂度排序，这种线性复杂度是用空间换的，即用空间换时间
6. 计数排序一个简答的例子：对一个班的考试成绩进行排名，一种做法就是统计处各个分数的人数，然后再累加
比如<=70的有25人，择71分排在位置26，简单来说，如果有10个元素小于X，则X的位置应该是11
- 计数排序假设元素>=0, 并且知道一个最大值的范围，假设最大值为K
- 需要一个大小为K+1的数组C来计数
- 需要一个大小为n的数组B来存放排序后的数据(n为元素个数)
package datastructure.sort;
import java.util.Arrays;
public class CountingSort {
public static void sort(int[] arr) {
int maxNum=Arrays.stream(arr).max().getAsInt();
int n=arr.length;
int[] C=new int[maxNum+1];
int[] B=new int[n];
for(int num:arr) {
C[num]++;//统计每个元素出现的次数
}
for(int i=1;i<=maxNum;i++) {
C[i]+=C[i-1];//C[i]表示<=i的元素的个数
}
System.out.println(Arrays.toString(C));
//这里从后往前处理是因为 对于5 5 5这种情况 先处理到后面的5 放到较后面的位置 保证稳定性
for(int i=n-1;i>=0;i--) {
int num=arr[i];
int cnt=C[num];//<=arr[i]的有cnt个
B[cnt-1]=num;//第cnt个位置（索引是cnt-1）放置arr[i]
C[num]-=1;//arr[i]待处理的数量减一 如果有多个的arr[i]的话 将会往前面放
}
System.out.println(Arrays.toString(B));
}
public static void main(String[] args) {
// int[] arr= {2,3,1,7,6,5,8,0,9,4};
int[] arr= {1,1,1,3,5,6,9,8,9,9,6,5,2,4,0};
sort(arr);
}
}
7. 桶排序
假设需要排序的元素：0.12 0.17 0.21 0.23 0.26 0.39 0.68 0.72 0.78 0.94
先创建一个大小为10的桶，每个桶中将映射到桶中的元素以链表的形式存放（类似于HashMap），然后对每个桶中的元素进行排序，排完序之后按顺序各个链表中的元素加入原数组中的即可
package datastructure.sort;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;
public class BucketSort {
public static final int BUCKETS=10;
public static void sort(double[] arr) {
ArrayList[] buckets=new ArrayList[BUCKETS];
for(int i=0;i
buckets[i]=new ArrayList<>();
}
int n=arr.length;
for(int i=0;i
int val=(int) (10*arr[i]);
buckets[val].add(arr[i]);//将元素加入对应的桶中
}
for(int i=0;i
Collections.sort(buckets[i]);//对桶中的链表进行排序
}
int index=0;
for(int i=0;i
System.out.println(buckets[i]);
for(int j=0;j
arr[index++]=buckets[i].get(j);//第i号桶中的第j个元素
}
}
}
public static void main(String[] args) {
int N=20;
Random random=new Random();
double[] arr=new double[N];
for(int i=0;i
arr[i]=random.nextDouble();
}
System.out.println("排序前："+Arrays.toString(arr));
sort(arr);
System.out.println("排序后:"+Arrays.toString(arr));
}
}
分析：假设有n个元素，有m个桶，元素平均分布在每个桶中，即每个桶中的元素个数是n/m, 则对每个桶中的元素进行快速排序，时间复杂度是
n
m
×
l
o
g
n
m
frac{n}{m} times logfrac{n}{m}
mn×logmn, 一共有m个桶，所以总的复杂度是：
m
×
n
m
×
l
o
g
n
m
=
n
l
o
g
n
m
mtimesfrac{n}{m} times logfrac{n}{m}=nlogfrac{n}{m}
m×mn×logmn=nlogmn
当桶的个数m足够多，比如等于n时，
n
l
o
g
n
m
=
n
nlogfrac{n}{m}=n
nlogmn=n , 这是最好的情况
如果极端情况n个元素落在一个桶中，则时间复杂度是
n
l
o
g
n
nlogn
nlogn
在桶排序中，对于每个桶中的元素不仅仅可以采用快速排序，也可以使用计数排序
8. 基数排序思想：
- 取每个元素的最低位
- 基于最低位对元素进行排序
- 对下一个最低位重复上述过程
用于处理数组元素是整数的情况，如果需要处理负数需要作相应处理
package datastructure.sort;
import java.util.Arrays;
public class RadixSort {
public static void radixSort(int arr[])
{
//先求出数组元素中最大数的位数
int max=Arrays.stream(arr).max().getAsInt();
int maxLength=(max+"").length();//最大数字的位数,转化为字符串求长度比较简单
int bucket[][]=new int[10][arr.length];//创建10个桶，每个桶的大小是原数组中元素的个数
//第一维是表示数字0-9 第二维是表示相应基数的元素的个数 0号桶到9号桶
int[] bucketElementCounts = new int[10];//记录每个桶中放的元素的个数
//bucketElementCounts[0]的数值就是0号桶中元素的个数 依次类推
for(int i=0,n=1;i
for(int j=0;j
int num=arr[j]/n%10;//获取当前位置的数字
//n=1时获取个位数字 n=10时获取十位数字....
int cnt=bucketElementCounts[num];//当前取余后的数字的num的元素个数
bucket[num][cnt]=arr[j];//将对应位置的数字放进对应的桶中
bucketElementCounts[num]++;//余数为num的元素个数+1
}
int index=0;
for(int j=0;j
if(bucketElementCounts[j]!=0)//当前j号桶中有元素
{
for(int k=0;k
int[] arr= {329,457,657,839,436,720,355};
radixSort(arr);
}
}
时间复杂度分析：
O
(
n
d
)
O(nd) quad
O(nd) d是最大数字的位数 n是数组元素个数
上面的代码采用了多个桶，当然也可以只使用计数排序按某一位进行排序（数值范围0-9）（要保证计数排序的稳定性），实际上可以看出计数排序就是桶排序中只有1个桶的情形
