一、排序的基本概念
- 排序：将一个数据元素集合或序列重新排列成按一个数据元素某个数据项值有序的序列
- 稳定排序：排序前和排序后相同元素的位置关系与初始序列位置一致（针对重复元素来说，相对位置不变）
- 不稳定排序：排序前和排序后相同元素的位置关系与初始序列相比发生改变
- 排序算法分类：
- 内部排序：将所有数据加载到内部存储器中完成，待排序序列完全存放在内存中的排序
插入排序：直接插入和希尔排序
选择排序：直接选择排序和堆排序
交换排序：冒泡排序和快速排序
归并排序
分配排序：桶排序，基数排序，计数排序
- 内部排序：将所有数据加载到内部存储器中完成，待排序序列完全存放在内存中的排序
- 外部排序：借助外部存储空间和内存进行排序，参与排序的数据非常多，数据量非常大，常用多路归并排序算法
- 衡量排序算法的优劣：
- 时间复杂度：分析关键字的比较次数和记录的移动次数
- 空间复杂度： 分析排序算法中需要多少辅助内存
- 稳定性： 若两个记录A和B的关键字值相等，但排序后A、 B的先后次序保持不变，则称这种排序算法是稳定的
- 算法的特征
| 输入（Input） | 有0个或多个输入数据，这些输入必须有清楚的描述和定义 |
| 输出（Output） | 至少有1个或多个输出结果，不可以没有输出结果 |
| 有穷性（有限性，Finiteness） | 算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤 可以在可接受的时间内完成 |
| 确定性（明确性，Definiteness） | 算法中的每一步都有确定的含义，不会出现二义性 |
| 可行性（有效性，Effectiveness） | 算法的每一步都是清楚且可行的，能让用户用纸笔计算而求出答案 |
- 排序算法比较
- 希尔排序最坏时间复杂度为N^s，1<s<2
冒泡、直接选择、直接插入排序需要两个for循环，每次只关注一个元素，平均时间复杂度为O(n²)）（一遍找元素O(n)，一遍找位置O(n)）
快速、归并、希尔、堆基于二分思想，log以2为底，平均时间复杂度为O(nlogn)（一遍找元素O(n)，一遍找位置O(logn)）
稳定性记忆-“快希选堆不稳定”（快牺牲稳定性）
二、直接插入排序
原理：把n个待排元素看成一个有序表和一个无序表，开始有序表里只有一个元素，无序表里有n-1个元素，每次从无序表去一个元素有序的插入到有序表的适当位置
- 步骤：
- 从第一个元素开始，将其视为已排序元素
- 取出下一个元素，在已经排好序的序列从后向前扫描
- 如果已排序的元素大于插入值，将排序元素移到下一位置
- 重复步骤，直到找到已排序的元素小于或等于插入值
- 将插入值放在找到的元素后面
package Oder;
import java.util.Arrays;
public class InsertSort {
public static void main(String[] args) {
//按升序
int[] arr={101,34,119,1,-1,89};
InsertSort.sort(arr);
System.out.println(Arrays.toString(arr));
}
private static void sort(int[] arr) {
//分成有序和无序两个数组
//每次比较，将无序查到有序的合适位置
for (int i = 1; i <arr.length ; i++) {
int insertValue= arr[i];
int insertIndex= i-1;
while (insertIndex>=0 && insertValue<arr[insertIndex] ){
arr[insertIndex+1]=arr[insertIndex];
insertIndex--;
}
if (insertIndex+1!=i)
{arr[insertIndex+1]=insertValue;}
} }
}
三、希尔排序
优先比较距离较远的元素。希尔排序又叫缩小增量排序
- 希尔排序的时间复杂度在O(nlog2n)~o(n^2)之间，大致为O(n^1.3)
- 由于希尔排序对每个子序列单独比较并进行元素交换，有可能改变相同元素的原始顺序，因此是不稳定排序
- 步骤
- 现将待排序序列分割成若干子序列（相隔某个“增量”的元素），然后进行直接插入排序
- 待整个子序列基本有序，在进行子序列的直接插入排序
- 增量的确定用gap=arr.length/2;gap>0;gap/=2
package Oder;
import java.util.Arrays;
public class Shell {
public static void main(String[] args) {
//按升序
int[] arr={8,9,1,7,2,5,3,4,6,0};
//Shell.changeSort(arr);
Shell.insertSort(arr);
System.out.println(Arrays.toString(arr));
}
private static void insertSort(int[] arr) {
//每次都是二分组
//每一组进行直接插入排序
//分组
for(int gap= arr.length/2;gap>0;gap/=2){
//直接插入排序
//确定无序组，有序表为前面的元素
for (int i=gap;i<arr.length;i++){
int index=i;
int val=arr[i];
while (index-gap>=0&&arr[index-gap]>val){
arr[index]=arr[index-gap];
index-=gap;
}
if (index!=i)
arr[index]=val;
}
}
}
}
四、直接选择排序
原理： 每次把最小值或者最大值放在指定位置，一开始从0~n-1区间上选择一个最小值与位置0 的元素交换，将其放在位置0上，然后在1~n-1范围上选取最小值放在位置1上。
- 无论初始状态如何，在第i趟排序中选择当前后续序列中最小的元素，因此比较的总次数为∑(n-i)=n(n-1)/2=O(n^2)
- 最好情况：序列已经排好序，移动次数为0
- 最坏情况：序列逆序，每次排序都要执行交换操作
- 由于直接选择排序中存在不相邻元素交换额可能性，因此是不稳定排序
package Oder;
import java.util.Arrays;
public class DirectSelectSort {
public static void main(String[] args) {
//按升序
int[] arr={3,-1,2,5,-2,10,7};
DirectSelectSort.sort(arr);
System.out.println(Arrays.toString(arr));
}
private static void sort(int[] arr) {
int temp=0;
for(int i=0;i<arr.length-1;i++){
int min=i;
for (int j= i+1;j<arr.length;j++){
if(arr[min]>arr[j]){
min=j;
}
}
System.out.println(i+ " "+ min);
if (min!=i){
temp=arr[i];
arr[i]=arr[min];
arr[min]=temp;
}
}
}
}
五、堆排序
堆排序是直接选择排序的优化，避免了重复比较，采用了树形选择排序，总的比较次数为O(nlog2n)，但需要增加额外的空间存放中间比较结果和排序结果
大顶堆：每个结点的值都大于或等于其左右孩子结点的值
小顶堆：每个结点的值都小于或等于其左右孩子结点的值
-
步骤：
建立初始堆：从n/2开始，它对应着二叉树的最后一个非叶子节点，将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
-
交换顶点元素，重新建堆
将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。
不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
- 在整个排序过程中，共需要进行n/2+n-1次筛选运算，每次筛选都要进行双亲和孩子或兄弟节点的比较，移动次数不会超过二叉树的深度log2n+1,因此时间复杂度为O(nlog2n),交换过程中可能导致重复元素位置变换，是不稳定排序
package Oder;
import java.util.Arrays;
public class HeapSort {
public static void main(String[] args) {
//按升序
int[] arr={3,-1,2,5,-2,10,7};
heapSort(arr);
}
private static void heapSort(int[] arr) {
/*adjustArray(arr, 1, arr.length);
adjustArray(arr,0,arr.length);*/
for (int i=arr.length/2-1;i>=0;i--){
adjustArray(arr,i,arr.length);
}
for (int j=arr.length-1;j>0;j--){
//先交换
int temp=arr[j];
arr[j]=arr[0];
arr[0]=temp;
adjustArray(arr,0,j);
}
System.out.println(Arrays.toString(arr));
}
private static void adjustArray(int[] arr, int i, int length) {
if (arr==null||arr.length==0)return;
int temp=arr[i]; //保存当前顶点值
for(int k= 2*i+1;k<length;k=2*k+1){
//每次都是把最左的节点当根
if (k+1<length && arr[k]<arr[k+1]){ //说明他的左节点小于右节点
k++;
}
if (arr[k]<temp){
break;
}else{
arr[i]=arr[k];
i=k;// 就把当前节点的最大值索引赋给了i
}
}
arr[i]=temp;
}
}
六、冒泡排序
原理：每次处理相邻逆序对，经过一次遍历后，最大的数或最小的数会被确定
一共进行n-1趟循环，每一趟排序次数会减少，因为有k个数据已经被确定，排序次数只有n-k-1
经K轮扫描交换，最大的K个元素必然就位，问题规模缩减至n-k
经过至多n 趟扫描后，排序必然终止
优化策略： 如果在某次循环中发现没有发生一次交换，说明已经排序好，可以提前结束，每趟循环判断flag
- 如果排序数组已经是有序的，冒泡排序只需要进行一趟比较即可退出，
- 如果是逆序，需要进行n-1次扫描，n(n-1)/2次比较，总共花费3(n^2-n)/2
- 冒泡排序不改变相同元素相对位置，是稳定排序算法
package Oder;
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
int[] arr={3,-1,2,5,-2,10,7};
//BubbleSort.sort(arr);
BubbleSort.sortBest(arr);
System.out.println(Arrays.toString(arr));
} private static void sort(int[] arr) {
//遍历次数
for(int i=0;i<arr.length-1;i++){
//一次遍历，将相邻逆序对全部转换，最小的元素排在最前面
for (int j=0;j<arr.length-1-i;j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
} //优化
private static void sortBest(int[] arr) {
int temp=0;
//遍历次数
for(int i=0;i<arr.length-1;i++){
boolean flag=false;
//一次遍历，将相邻逆序对全部转换，最小的元素排在最前面
for (int j=0;j<arr.length-1-i;j++) {
if (arr[j] > arr[j + 1]) {
flag=true;
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
System.out.println(i);
if (!flag) break;
}
}
}
七、快速排序
原理：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
- 步骤
从数列中挑出一个元素，称为 “基准”（pivot）；
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
- 快速排序需要一个栈存放每次调用的指针和参数，最大调用次数与递归树的高度一致，理想情况为O(nlog2(n+1)),最坏情况是O(n^2),是不稳定排序
package Oder;
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] arr={8,9,1,2,2,5,3,2,6,0};
QuickSort.sort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
private static void sort(int[] arr, int left, int right) {
//二分法，取中间值作为分界点，左边的比他都小，右边的都比他大，r指代左边的最右边界，l指代右边的最左边界
int pivot=arr[(left+right)/2];
int l =left;
int r=right;
while (l<r){
while(arr[l]<pivot){
//找到左边第一个大于中值的
l++;
}
while (arr[r]>pivot){
//找到右边第一个中值的
r--;
}
//如果左边坐标比右边大，说明不用排了，已经找过界了
// 否则就交换二者值
if(l<r){
int temp= arr[l];
arr[l]=arr[r];
arr[r]=temp;
}else break;
if (arr[l]==pivot)r-=1;
if (arr[r]==pivot) l+=1;
}
if (l==r){
r-=1;
l+=1;
}
if (left<r)
sort(arr,left,r);
if (right>l)
sort(arr,l,right);
}
}
- 递归优化
package Oder;
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] arr={ 47,29,71,99,78,19,24,47};
QuickSort.sort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
private static void sort(int[] arr, int left, int right) {
//- 从数列中挑出一个元素，称为 “基准”（pivot）；
if (left<right)
{int pivot=partition(arr,left,right);
sort(arr,left,pivot-1);
sort(arr,pivot+1,right);}
}
private static int partition(int[] arr, int left, int right) {
int mid=left;
int index=left+1; //轮换法，不是一个一个移
for(int i=index;i<=right;i++){
if (arr[i]<arr[mid]){
swap(arr,i,index); //index一定只是比mid数组元素大的那个索引位置
index++; //每交换一次，index后移一位
}
}
swap(arr,mid,index-1);//将中间值就位
return index-1;
}
private static void swap(int[] arr, int left, int right) {
int temp= arr[left];
arr[left]=arr[right];
arr[right]=temp;
}
}
package Oder;
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] arr={ 47,29,71,99,78,19,24,47};
//Shell.changeSort(arr);
QuickSort.sort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
private static void sort(int[] arr, int left, int right) {
if (left<right){
int mid= quicksort(arr,left,right);
sort(arr,left,mid-1);
sort(arr,mid+1,right);
}
}
private static int quicksort(int[] arr, int left, int right) {
int pivot =arr[left];
int index=left+1;
while(index<=right){
//注意数组溢出的可能性
while (index<=right&&arr[index]<=pivot) index++;//从左找到比基准值大的
while (index<=right&&arr[right]>=pivot) right--;//从右找到第一个比基准值小的
if (index>=right) break;
else swap(arr,index,right);
}
arr[left]=arr[right];
arr[right]=pivot;
return right;
}
private static void swap(int[] arr, int left, int right) {
int temp= arr[left];
arr[left]=arr[right];
arr[right]=temp;
}
}
八、归并排序
归并排序是将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
-
步骤
把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。
- 归并排序的时间复杂度为O(nlogn)，空间复杂度是O(n)，是稳定排序
package Oder;
import java.util.Arrays;
public class MergeSort {
private static int count=0;
public static void main(String[] args) {
int[] arr={ 47,29,89,6,78,2,-9};
int [] temp= new int[arr.length];
MergeSort.mergesort(arr,0,arr.length-1,temp);
System.out.println(Arrays.toString(arr));
System.out.println(Arrays.toString(temp));
}
private static void mergesort(int[] arr, int left, int right, int[] temp) {
if (left<right){
int mid= (left+right)/2;
//先分组
//每次分组分为左右两个组
mergesort(arr,left,mid,temp);
mergesort(arr,mid+1,right,temp);
//在合并
merge(arr,left,mid,right,temp);
}
}
private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
//比较相邻逆序对
int i=left;
int j= mid+1;
int k=0;
while (i<=mid&&j<=right)
{if (arr[i]<arr[j]){
temp[k]=arr[i];
k++;
i++;
}else {
temp[k]=arr[j];
k++;
j++;
}
}
while (i<=mid){
temp[k++]=arr[i++];
}
while (j<=right){
temp[k++]=arr[j++];
}
k=0;
int start= left;
while (start<=right){
arr[start++]=temp[k++];
}
System.out.println(++count);
}
}
九、计数排序
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
-
步骤
找出待排序的数组中最大和最小的元素；
统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。
当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。
package Oder;
import java.util.Arrays;
public class CountSort {
public static void main(String[] args) {
int[] arr={ 47,29,71,99,78,19,24,47};
CountSort.sort(arr);
System.out.println(Arrays.toString(arr));
}
private static void sort(int[] arr) {
//先找最大值和最小值
int max= arr[0];
int min =arr[0];
for (int i=0;i<arr.length;i++){
if (max<arr[i]){
max=arr[i];
}
if (arr[i]<min){
min=arr[i];
}
}
//定义最大值和最小值之间的数组
int size= max-min+1;
int[] nums= new int[size];
//有多少个相同的元素就++
for (int i=0;i<arr.length;i++){
nums[arr[i]-min]++;
}
//System.out.println(Arrays.toString(nums));
//还原数组，遍历并--
int index=0;
for(int i=0;i<size;i++){
while (nums[i]>0){
arr[index++]=i+min;
nums[i]--;
}
}
}
}
十、桶排序
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。
原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）
-
步骤
设置一个定量的数组当作空桶；
遍历输入数据，并且把数据一个一个放到对应的桶里去；
对每个不是空的桶进行排序；
从不是空的桶里把排好序的数据拼接起来。
桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。
桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大
package Oder; import javax.print.DocFlavor;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections; public class BucketSort {
public static void main(String[] args) {
int[] arr={ 47,29,71,-99,78,19,24,47};
BucketSort.sort(arr);
System.out.println(Arrays.toString(arr));
} private static void sort(int[] arr) {
//先找到最大值和最小值
int max= arr[0];
int min =arr[0];
for (int i=0;i<arr.length;i++){
if (max<arr[i]){
max=arr[i];
}
if (arr[i]<min){
min=arr[i];
}
}
//确定桶的数量，桶的数量分的越多，内部桶的排序就越快
int bucketNum= (max-min)/arr.length+1;
//创建桶链表
ArrayList<ArrayList<Integer>> bucket=new ArrayList<>(bucketNum);
for (int i=0;i<bucketNum;i++){
bucket.add(new ArrayList<>());
}
//- 遍历输入数据，并且把数据一个一个放到对应的桶里去；商相等的属于同一层级
for (int i=0;i<arr.length;i++){
bucket.get((arr[i]-min)/arr.length).add(arr[i]);
}
System.out.println(bucket);
//- 对每个不是空的桶进行排序；
for (int i=0;i<bucketNum;i++){
Collections.sort(bucket.get(i));
}
//- 从不是空的桶里把排好序的数据拼接起来。
int index=0;
for (int i=0;i<bucketNum;i++){
for (int j=0;j<bucket.get(i).size();j++){
arr[index++]=bucket.get(i).get(j);
}
} }
}
十一、基数排序
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。
有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
-
步骤
取得数组中的最大数，并取得位数；
arr为原始数组，从最低位开始取每个位组成radix数组；
对radix进行计数排序（利用计数排序适用于小范围数的特点）；
-
对负数的处理不适用于基数排序，要对负数进行一个转换
如果有负数，就找到最小值，将数组的每一位都加上一个填充数使得最小值为0，最后填回数组时在将每一位填充数减去
将该数组分成负数数组和非负数数组，分别进行基数排序，然后将负数的数组翻转，最后合并
package Oder;
import java.util.Arrays;
public class RadixSort {
public static void main(String[] args) {
int[] arr={ 47,29,-71,99,-78,19,-24,47};
RadixSort.sort(arr);
System.out.println(Arrays.toString(arr));
}
private static void sort(int[] arr) {
//最大值和先找最小值
int max = arr[0];
int min = arr[0];
for (int i = 0; i < arr.length; i++) {
if (max < arr[i]) {
max = arr[i];
}
if (arr[i] < min) {
min = arr[i];
}
}
//如果最小值为负数，则进行处理，加填充数
int addnum = 0;
if (min < 0) {
addnum = -min;
}
for (int i = 0; i < arr.length; i++) {
arr[i] += addnum;
}
//这里就都变成了正数了，最大值也相应的变成了 max+addnum
max += addnum;
//- 取得数组中的最大数，并取得位数；
int digit = 0;
while (max > 0) {
digit++;
max /= 10;
}
System.out.println(digit);
//- arr为原始数组，从最低位开始取每个位组成radix数组；
//10个桶，每一个桶存放是该位数的数组元素,最坏情况下都在一个桶里，那该桶元素就arr.length个
int[][] bucket = new int[10][arr.length];
int[] bucketcount = new int[10];
for (int i = 0, n = 1; i < digit; i++, n *= 10) {
for (int j = 0; j < arr.length; j++) {
bucket[arr[j] / n % 10][bucketcount[arr[j] / n % 10]] = arr[j];
bucketcount[arr[j] / n % 10]++;
}
//还原
int index = 0;
for (int k = 0; k < arr.length; k++) {
if (bucketcount[k] != 0) {
for (int j = 0; j < bucketcount[k]; j++) {
arr[index++] = bucket[k][j];
}
}
bucketcount[k] = 0;
}
}
for (int i = 0; i < arr.length; i++) {
arr[i] -= addnum;
}
}
}
十二、总结
- 内部排序方法性能比较
- 从平均时间而言，快速排序最快，但在最坏情况下不如堆排序和归并排序
- 从算法简单性而言， 直接选择排序、直接插入、冒泡排序算法简单
- 从稳定性而言，快速排序，希尔排序，直接选择排序，堆排序是不稳定的
- 排序方法选择
- 当待排序数目较大时，若要求排序稳定，选择归并排序
- 当待排序数目较大，分布随机，不要求稳定，选择快速排序
- 当待排序数目较大，关键字会出现正序、逆序，采用堆排序
- 当待排序数目较小时，记录已接近有序或随机分布，要求排序稳定，选择直接插入排序
- 当待排序数目较小，不要求稳定，采用直接选择排序
- 若文件初始状态基本有序(指正序)，则应选用直接插入、 冒泡或随机的快速排序