稳定性
假设在待排序的序列中，存在多个具有相同关键字的记录，若经过排序，这些记录的相对顺序保持不变，即在原序列中，ri=rj且ri在rj之前；在排序后的序列中，ri仍在rj之前，则称这种算法是稳定的，否则称为不稳定的
稳定性的意义：排序算法如果是稳定的，那么从一个键上排序，然后再从另外一个键上排序，第一个键排序的结果可以为第二个键排序所用
排序算法总结
归并排序
首先递归将原始数组划分为若干子数组，对每个子数组进行排序。然后将排好序的子数组合并成一个有序的数组。归并排序示意图
/**
* 代码实现
*/
//将两个有序数组合并
public static void mergeArray(int[] arr,int start,int middle,int end,int[] tmp){
int i=start;
int j=middle;
int m=middle+1;
int n=end;
int k=0;
while (i<=j && m<=n){
if (arr[i]<arr[m]){
tmp[k]=arr[i];
k++;
i++;
}else{
tmp[k]=arr[m];
k++;
m++;
}
}
while (i<=j){
tmp[k]=arr[i];
i++;
k++;
}
while (m<=n){
tmp[k]=arr[m];
k++;
m++;
}
//将原数组的值替换为新数组的值
for (int s=0;s<k;s++){
arr[start+s]=tmp[s];
}
}
//递归的查分数组
public static void mergeSort(int[] arr,int start,int end,int[] tmp){
if (start<end){
int middle=(start+end)/2;
mergeSort(arr,start,middle,tmp);//左半数组排好序
mergeSort(arr,middle+1,end,tmp);//右半数组排好序
mergeArray(arr,start,middle,end,tmp);//合并数组
}
}
public static void main(String[] args) {
int[] arr={6,4,8,1,5,9};
int[] tmp=new int[arr.length];
mergeSort(arr,0,arr.length-1,tmp);
System.out.println(Arrays.toString(arr));
}
冒泡排序
过程：
- 比较相邻两个数，如果后一个数比前一个数小，就交换两者位置
- 从后往前比较，一直到最前面的数据，这样数组中最小的数就到达了最前面
- 重复上述过程arr.length-1次直到所有数据排序完成
优化： 数据的顺序排好之后，冒泡排序仍会进行下一轮的比较，后面的比较是没有意义的，设立标志flag，如果发生了交换，flag设置为true，如果没有发生交换，flag为false，当一轮比较结束后flag仍为false意味着数组已经有序，结束冒泡排序
/**
* 冒泡排序代码实现
*/
public static void BubbleSort(int[] arr){
for (int i=0;i<arr.length-1;i++){//表示趟数
boolean flag=false;
for (int j=arr.length-1;j>i;j--){
if (arr[j]<arr[j-1]){
int tmp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=tmp;
flag=true;
}
}
//一轮循环结束
if (flag==false){
break;
}
}
}
选择排序
基本思想：
- 在长度为N的无序数组中，第一次遍历N个数，找到最小值与第一个元素交换
- 第二次遍历N-1个元素，找到最小的值与第二个元素交换
- 第N-1次遍历，找到最小的元素与第N-1个元素交换
/**
* 选择排序代码实现
*/
public static void selectSort(int[] arr){
for (int i=0;i<arr.length-1;i++){
int minIndex=i;//最小值的下标
int min=arr[i];//最小值
for (int j=i+1;j<arr.length;j++){
if (arr[j]<min){
minIndex=j;
min=arr[j];
}
}
//交换位置
if (minIndex!=i){
arr[minIndex]=arr[i];
arr[i]=min;
}
}
}
插入排序
基本思想：
在要排序的一组数中，假定前N-1个数已经排好序，现在将第N个数插入到前面的有序数组中，使得这N个数也是有序的，如此循环直到全部排好序
/**
* 插入排序代码实现
*/
public static void insertSort(int[] arr){
for (int i=0;i<arr.length-1;i++){
for (int j=i+1;j>0;j--){
if (arr[j]<arr[j-1]){
//交换位置
int tmp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=tmp;
}else {
//说明前面数已经有序了
break;
}
}
}
}
快速排序
1、先从数组中取出一个数作为基准元素
2、分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边
3、再对左右区间重复上述过程，直到各区间只有一个数
当序列中的数字是完全倒序的时候退化成冒泡排序
public static int partition(int []array,int lo,int hi){
//固定的切分方式
int key=array[lo];
while(lo<hi){
while(array[hi]>=key&&hi>lo){//从后半部分向前扫描
hi--;
}
array[lo]=array[hi];
while(array[lo]<=key&&hi>lo){从前半部分向后扫描
lo++;
}
array[hi]=array[lo];
}
array[hi]=key;
return hi;
}
public static void sort(int[] array,int lo ,int hi){
if(lo>=hi){
return ;
}
int index=partition(array,lo,hi);
sort(array,lo,index-1);
sort(array,index+1,hi);
}
堆排序
我们以大顶堆为例，初始时把要排序的序列构建成一个大顶堆。然后将根节点与最后一个节点交换，对前面n-1个数重新调整使之成为堆，依次类推，最后得到n个节点的有序序列。
建堆时间复杂度为O(n)，调整堆时间复杂度为O(nlgn)
//不稳定
import java.util.Arrays;
public class HeapSort {
public static void main(String[] args) {
int[] a={49,38,65,97,76,13,27,49,78,34,12,64};
int arrayLength=a.length;
//循环建堆
for(int i=0;i<arrayLength-1;i++){
//建堆
buildMaxHeap(a,arrayLength-1-i);
//交换堆顶和最后一个元素
swap(a,0,arrayLength-1-i);
System.out.println(Arrays.toString(a));
}
}
//对data数组从0到lastIndex建大顶堆
public static void buildMaxHeap(int[] data, int lastIndex){
//从lastIndex处节点（最后一个节点）的父节点开始
for(int i=(lastIndex-1)/2;i>=0;i--){
//k保存正在判断的节点
int k=i;
//如果当前k节点的子节点存在
while(k*2+1<=lastIndex){
//k节点的左子节点的索引
int biggerIndex=2*k+1;
//如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在
if(biggerIndex<lastIndex){
//若果右子节点的值较大
if(data[biggerIndex]<data[biggerIndex+1]){
//biggerIndex总是记录较大子节点的索引
biggerIndex++;
}
}
//如果k节点的值小于其较大的子节点的值
if(data[k]<data[biggerIndex]){
//交换他们
swap(data,k,biggerIndex);
//将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值
k=biggerIndex;
}else{
break;
}
}
}
}
//交换
private static void swap(int[] data, int i, int j) {
int tmp=data[i];
data[i]=data[j];
data[j]=tmp;
}
}
希尔排序
基本思想：在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。然后逐渐将增量减小，并重复上述过程，直至增量为1，此时数据序列基本有序，最后进行插入排序。
希尔排序示意图
基数排序
基本思想：将所有待比较的数值统一为同样的数位长度，数位较短的数前面补0。然后从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成了一个有序数列
基数排序示意图
