数据结构算法——排序算法

1.排序

1.选择排序

不稳定，一般不用，基本排序

思路：过滤数组，找到最小数，放在前面。

不稳：导致原本在前的数据移动到后面。

	int arr[];for(i=0;i<arr.length-1;i++){int smallest=i;			for(j=i+1;j<length;j++){	if(arr[j]<arr[smallest]){smallest=j;}swap(arr,i,smallest);}}

时间复杂度O(n2)，空间复杂度O(1)

2.冒泡排序

稳定，不常用，太慢，基本排序

思路：从第一个数两两比较，然后大的向后交换位置。

	int arr[];for(i=arr.length-1;i>0;i--){for(j=0;j<i;j++){if(arr[j]>arr[j+1]){swap[arr,j,j+1]}}}

时间复杂度O(n2)，空间复杂度O(1)

3.插入排序

稳定，三种基本排序中最常用，在数据较少且有一定次序时效率很高

思路：从第二位向后过滤，向前逐位比较并与更小的交换直到大于或等于。

	int arr[];for(i=1;i<arr.length-1;i++){for(j=i;i>0;i--){if(arr[j-1]>arr[j]) swap(arr,j-1,j);}}

时间复杂度O(n2)，空间复杂度O(1)

4.希尔排序

稳定，是优化过的插入排序

思路：按一定数据间隔将数据分组进行插入排序，然后缩小间隔进行，直到为1。

问：为什么比插入排序更优？

答：分组大时，换位次数少。分组小时，换位距离短。

	int arr[];int h=1;while(h<=arr.length/3){h=h*3+1;			//计算Knuth数列}for(gap=h;gap>0;gap=(gap-1)/3){		//缩小间隔for(i=gap;i<arr.length;i++){for(j=i;j>gap-1;j-=gap){if(arr[j-gap]>arr[j]) swap(arr,j-gap,j);	//每组进行插入排序}}

时间复杂度O(n^1.3)，空间复杂度O(1)

5.归并排序

稳定，对于预先有一定次序的数组效率很高

思路：将数组递归地分为两部分，然后两个部分中的数依次比较，较小的填入中间数组。

public void sort(int[] arr,left,right){if(left==right) return;			//边界判定，何时停止int mid=left-(left+right)/2;		//递归中点计算sort(arr,left,mid);					//左侧递归sort(arr,mid+1,right);				//右侧递归merge(arr,left,mid,right);			//进行分组排序print(arr);
}	public void merge(int[] arr,leftPtr,rightPtr,rightBound){int temp[]=new int[leftPtr-rightBound+1];		//定义中间数组int i=leftPtr;		//定义左指针，右指针int j=rightPtr;int k=-1;while(i<rightPtr&&j<rightBound){temp[k++] = arr[i] <= arr[j] ? arr[++i] : arr[++j];		//将左指针和右指针指向的数小的放入中间数组}	while(i<rightPtr-1) temp[k++]=arr[i++];		//将左侧剩余数放入中间数组while(j<rightBound) temp[k++]=arr[j++];			//将右侧剩余数放入中间数组for(int m=0;m<temp.length;m++) arr[leftPtr+m]=temp[m];			//将中间数组放入原数组
}

时间复杂度O(N log N)，空间复杂度O(N)

6.快速排序

不稳

原理：选出一个数，将比它小的数放到它左侧，比它大的数放到它右侧。

可优化位双轴快速排序（java中对较大数组的排序方法）

/*
*@param left 左边界
*@param right 右边界
*/
public void sort(arr[],left,right){		//边界判断if(left>=right) return;		//初始化左右指针int i=left;						int j=right;//将最后一位定为pivotint pivot=arr[right];			while(i<j){//如果左侧比pivot大，则与右侧比pivot小的换位while(arr[i]<=pivot) i++;	while(arr[j]>pivot) j--;//如果左指针大于等于右指针说明本次排序结束if(i>=j) break;swap(arr,i,j);}if(arr[i]<=pivot){swap(arr,i+1,right);			//将pivot放在中间，此时，左侧比pivot小，右侧比pivot大}else{swap(arr,i,right);}sort(arr[],left,i-1);			//左侧递归sort(arr[],i,right);			//右侧递归
}

时间复杂度O(N log N)，空间复杂度O(1)

7.计数排序

桶排序的一种，非比较排序，稳定（优化后），对于数量大但数据大小数量少的情况效率很高

思路：将每种数据的数量放入中间数组中，然后按放回原数组中。

	int arr[];//进行取数组最大值，最小值的步骤，在此处省略，并初始化min，max为最小最大值int max;int min;sort(arr,max,min){int count=new int[max-min+1];		//设置计数桶int temp[arr.length];				//初始化中间数组for(i=0;i<arr.length;i++){count[arr[i]-min]++;			//计数}for(j=0;j<count.length;j++){count[j+1]+=count[j];			//优化步骤，此时桶中存储的是该数据最后一位的位置}for(k=arr.length;k>=0;k--){temp[--count[ arr[k]-min ]] = arr[k];		//优化步骤，从原数组最后开始过滤，将数据放到对应位置}return temp;}

时间复杂度O(N+K)，空间复杂度O(N+K)  （K是计数桶大小）

8.基数排序

桶排序的一种，非比较排序，基于技术排列，稳定

思路：对数据每一位上进行计数排列

从最低位开始的基数排序

	int arr[];//对最高位进行计算，此处跳过此步骤，直接初始化变量h为最高位数int h;sort(arr,h){int count=new int[10];		//设置计数桶，此时只有0-9int temp[arr.length];				//初始化中间数组for(m=0;m<h;m++){int divison=(int)Math.pow(10,m);		//求10的m次幂for(i=0;i<arr.length;i++){count[arr[i]/divison%10]++;			//计数}for(j=0;j<count.length-1;j++){			//优化步骤，此时桶中存储的是该数据最后一位的位置count[j+1]+=count[j];			}for(k=arr.length;k>=0;k--){				//优化步骤，从原数组最后开始过滤，将数据放到对应位置temp[--count[arr[k]]]=arr[k];		}}return temp;}

从最高位开始的基数排序

递归思想

	int arr[];//对最高位进行计算，此处跳过此步骤，直接初始化变量h为最高位数int h;sort(arr,h){if(h=1) return temp;int divison=(int)Math.pow(10,h);		//求10的i次幂int count=new int[10];		//设置计数桶，此时只有0-9int temp[arr.length];				//初始化中间数组for(i=0;i<arr.length;i++){count[arr[i]/divison%10]++;			//计数}for(j=0;j<count.length-1;j++){			//优化步骤，此时桶中存储的是该数据最后一位的位置count[j+1]+=count[j];			}sort(arr,h-1);for(k=arr.length;k>=0;k--){				//优化步骤，从原数组最后开始过滤，将数据放到对应位置temp[--count[arr[k]]]=arr[k];		}}

时间复杂度O(N_K)，空间复杂度O(N_K)  （K是计数桶大小）

9.桶排序

不常用，效率低

思路：将数据区域分为几个“桶”，将数据放入对应的“桶”中，对每个桶进行排序（其他排序方法或者递归）。

10.堆排序

堆排序是利用堆这种数据结构设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为 O(NlogN)，不稳定

思路：将数组转换成一个堆（视情况使用大顶堆或者小顶堆，此处为大顶堆），将最大值下沉（第一位和最后一位换位），将其他位数转换成堆，直到数组有序。

public static void heapSort(int arr[]) {int temp = 0;for(int i = arr.length / 2 -1; i >=0; i--) {adjustHeap(arr, i, arr.length);}for(int j = arr.length-1;j >0; j--) {swap(i,j);adjustHeap(arr, 0, j);}
}//将一个数组(二叉树), 调整成一个大顶堆
/**
* 功能： 完成 将 以 i 对应的非叶子结点的树调整成大顶堆
* @param arr 待调整的数组
* @param ptr 表示非叶子结点在数组中索引
* @param length 表示对多少个元素继续调整， length 是在逐渐的减少
*/
public static void adjustHeap(int arr[], int ptr, int length) {// k = ptr * 2 + 1 k 是 ptr 结点的左子结点for(int k = ptr * 2 + 1; k < length; k = k * 2 + 1) {//判断，避免遍历左右子树if(k+1 < length && arr[k] < arr[k+1]) { //如果左子节点比右子节点小，则转向右子节点k++; 									}//子节点判断if(arr[k] > arr[ptr]) { 	swap(arr,ptr,j) 	ptr = k; 				//对子树进行调整，避免结构混乱} else {break;}}
}

时间复杂度 O(N*Log N)，空间复杂度O(1)