排序算法
2018-10-13 本文已影响0人
pluss
常用排序算法总结(一)
找出数组中出现次数最多的那个数——主元素问题
Arrays.sort() 对基本类型用快速排序，非基本类型用归并排序，是因为基本类型不需要稳定性的排序，他们的相同值是无差别的。
Collections.sort()使用的Arrays.sort()
-
堆排序
堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。
其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，
而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)...1]逐步递减，近似为nlogn。
所以堆排序时间复杂度一般认为就是O(nlogn);
最坏最好都是O(nlogn);
辅助空间O(1);
不稳定; -
快速排序
快速排序每次递归取一个标准值，根据它来划分序列，划分总的再递归划分左右序列。
时间复杂度是O(nlogn);
最好是O(nlogn);
最坏是O(n^2);倒序，此时需要随机取标准值p。
因为递归划分序列，所以辅助空间O(logn)~O(n)
不稳定 -
归并排序
归并排序，递归平分序列到最底层（最底层只有一个数默认是排好序的），然后归并左右序列。
时间复杂度是O(nlogn);
最好最坏都是O(nlogn);
辅助空间O(n);
稳定
-
直接选择排序
暴力排序，每次遍历数组选出一个最大值
最好最坏都是O(n^2)
辅助空间O(1);
不稳定; -
直接插入排序
外循环从左到右i，
内循环比较当前值和后面的值，小于就交换（可以保存当前值，然后把要交换的值直接右移一位，不用真的去交换），否则退出循环
0到i始终有序
最好O(n)
最坏O(n^2)
平均O(n^2)
辅助空间O(1)
稳定- 改进：二分插入排序，如果比较的代价比交换的代价大的话，就可以使用这个算法减少比较次数，最优O(nlogn);
二分法在左边序列中定位当前值要插入的位置，把该位置右边的值都向右移动一个位置，插入。
- 改进：二分插入排序，如果比较的代价比交换的代价大的话，就可以使用这个算法减少比较次数，最优O(nlogn);
-
冒泡排序
外循环从大到小 j
内循环从0到j，当前值和前面的值比较，大于就交换。
每次内循环结束最大值都会浮到最上方。
最坏是O(n^2);
设一个标记标记内循环有没交换过，可以把最优时间复杂度降到O(n);
稳定;- 改进：鸡尾酒排序（定向冒泡排序）， 与冒泡排序不同在从低到高然后从高到低。以序列(2,3,4,5,1)为例，鸡尾酒排序只需要访问一次序列就可以完成排序，但如果使用冒泡排序则需要四次。但是在乱数序列的状态下，鸡尾酒排序与冒泡排序的效率都很差劲。
void CocktailSort(int A[], int n)
{
int left = 0; // 初始化边界
int right = n - 1;
while (left < right)
{
for (int i = left; i < right; i++) // 前半轮,将最大元素放到后面
{
if (A[i] > A[i + 1])
{
Swap(A, i, i + 1);
}
}
right--;
for (int i = right; i > left; i--) // 后半轮,将最小元素放到前面
{
if (A[i - 1] > A[i])
{
Swap(A, i - 1, i);
}
}
left++;
}
}
- 希尔排序
- 基数排序（桶排序？）
- 计数排序？
堆排序
package sort;
import java.util.Arrays;
/**
* 堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。
* 其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，
* 而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)...1]逐步递减，近似为nlogn。
* 所以堆排序时间复杂度一般认为就是O(nlogn);
* 最坏最好都是O(nlogn);辅助空间O(1);不稳定；
*/
public class HeapSort {
public static void main(String []args){
int []arr = {9,10,7,6,5,4,3,2,1};
sort(arr);
System.out.println(Arrays.toString(arr));//[1, 2, 3, 4, 5, 6, 7, 9, 10]
}
public static void sort(int[] arr) {
//先构建大顶堆 O(n)
//从最后一个非叶子节点开始 length/2-1
//从下至上，从右到左
for(int i =arr.length/2-1;i>=0;i--) {
adjustHeap(arr,i,arr.length);
}
//调整堆结构，交换堆顶元素与末尾元素
for(int i=arr.length-1;i>0;i--) {
swap(arr,0,i);
adjustHeap(arr,0,i);
}
}
/**
* 调整最大堆
* 堆大小小于等于3的可以当做是最大堆，所以构建最大堆时可以调用这个方法从下到上调整
* 循环子层直到子节点不大于父节点。
* @param arr 数组
* @param i 父节点
* @param length 要调整的数组长度，0~length-1
*/
public static void adjustHeap(int[] arr,int i,int length){
//如果子结点大于父结点的话，交换两者的位置，又因为交换之后又要判断下一层的父结点和子节点
//所以可以先把当前节点存起来，等到都比较好位置调好后，再把这个数值放在可以覆盖的节点上。
//i的左子节点是2i+1
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指向右子结点
k++;//k指向最大的子结点
}
if(arr[k]>temp) {//如果子结点大于父结点的话，将子结点赋给父结点
arr[i]=arr[k];
i=k;//继续下一层的判断，下一层的父结点还是temp
}else {
break;//如果子结点小于等于父结点的话，就不需要再调整堆了
}
}
arr[i]=temp;
}
public static void swap(int[] arr,int a,int b) {
int temp=arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
快速排序
package sort;
import java.util.Arrays;
import java.util.Random;
import java.util.Stack;
/**
* 快速排序每次递归取一个标准值，根据它来划分序列，划分总的再递归划分左右序列。
* 时间复杂度是O(nlogn);
* 最好是O(nlogn);
* 最坏是O(n^2);倒序，此时需要随机取标准值p。
* 因为递归划分序列，所以辅助空间O(logn)？？
*/
public class QucikSort {
public static void main(String []args){
int []arr = {9,10,7,6,5,4,3,2,1};
sort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
/**
* 从上到下递归，先划分总的，再划分左右序列
* @param arr
* @param start
* @param end
*/
public static void sort(int[] arr,int start,int end) {
if(start>=end){
return;
}
int i = partition(arr,start,end);
sort(arr,start,i-1);
sort(arr,i+1,end);
}
//非递归实现，用栈存start和end
public static void sortStack(int[] arr){
Stack<Integer> stack = new Stack<Integer>();
stack.push(0);
stack.push(arr.length-1);
while (!stack.isEmpty()){
int end = stack.pop();
int start = stack.pop();
int i = partition(arr,start,end);
if(start<i-1){
stack.push(start);
stack.push(i-1);
}
if(end>i+1){
stack.push(i+1);
stack.push(end);
}
}
}
/**
* 根据选定的标准p来划分序列，小于p的放左边，大于p的放右边，p在中间
* 头尾指针实现
* @param arr 待划分数组
* @param start 要开始划分的下标
* @param end 结束划分的下标
* @return 返回最后p所在的下标
*/
private static int partition(int[] arr,int start,int end){
if(start>=end){
return start;
}
int ran = (int)(Math.random()*(end-start+1))+start;//随机取标准值p
swap(arr,ran,start);
int p = arr[start];
int i = start; // 两个指针，右边指针先开始移动，碰到小于p的数时把它放到左边指针的位置；然后开始移动左指针，操作相反；两指针轮流移动直到i>=j。
int j = end;
while(i<j){
while (i<j&&arr[j]>=p){
j--;
}
arr[i]=arr[j];
while (i<j&&arr[i]<=p){
i++;
}
arr[j]=arr[i];
}
arr[i]=p;
return i;
}
private static void swap(int[] arr,int a,int b){
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
归并排序
package sort;
import java.util.Arrays;
/**
* 归并排序，递归平分序列到最底层（最底层只有一个数默认是排好序的），然后归并左右序列
* 时间复杂度是O(nlogn);
* 最好最坏都是O(nlogn);
* 辅助空间O(n);
* 稳定
*/
public class MergeSort {
public static void main(String []args){
int []arr = {9,10,7,6,5,4,3,2,1};
// sort(arr,0,arr.length-1);
sortIteration(arr);
System.out.println(Arrays.toString(arr));
}
//非递归实现
public static void sortIteration(int[] arr){
//从底到上
int left;
int mid;
int right;
for(int i=1;i<arr.length;i*=2) {//子序列大小，每轮乘2
left = 0;
while(left+i<arr.length) {//后一个子序列存在的话，归并两个序列
mid = left+i-1;
right = mid+i;
right = right<arr.length?right:arr.length-1;
merge(arr,left,mid,right);
left = right+1;
}
}
}
public static void sort(int[] arr,int start,int end) {
if(start>=end){
return;
}
int h = (start+end)/2;
sort(arr,start,h);
sort(arr,h+1,end);
merge(arr,start,h,end);
}
private static void merge(int[] arr,int start,int h,int end){
int i = start;//左序列，start~h
int j = h+1;//有序列，h+1~end
int[] aux = new int[end-start+1];//辅助数组
int k = 0;
while (i<=h&&j<=end){
while (i<=h&&j<=end&&arr[i]<=arr[j]) {
aux[k++]=arr[i++];
}
while (i<=h&&j<=end&&arr[j]<arr[i]) {
aux[k++]=arr[j++];
}
}
while (i<=h){
aux[k++]=arr[i++];
}
while (j<=end){
aux[k++]=arr[j++];
}
System.arraycopy(aux,0,arr,start,aux.length);
}
private static void swap(int[] arr,int a,int b){
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
