数据结构——排序

public static void insertSort(int[] array){
    for(int i=1;i<array.length;i++){
        int tmp=array[i];
        int j=i-1;
        while(j>=0){
            if(array[j]>tmp){
                array[j+1]=array[j];
            }else{
                break;
            }
            j--;
        }
        array[j+1]=tmp;
    }
}

3.性质

稳定性：稳定
时间复杂度：O(N^2)
空间复杂度：O(1)

注：元素集合越接近有序直接插入排序算法的时间效率越高

3、希尔排序缩小增量排序

1.操作

先选定一个整数把待排序元素中所有元素分成多个组所有距离为该整数的元素分在同一组内并对每组内的元素进行排序。然后再重复以上过程直到之前选的整数减为1此时所有元素完成排序。

2.代码

public static void shellSort(int[] array){
    int gap=array.length;
    while(gap>0){
        shell(array,gap);
        gap/=2;
    }
}
public static void shell(int[] array,int gap){
    for(int i=gap;i<array.length;i++){
        int tmp=array[i];
        int j=i-gap;
        while(j>=0){
            if(array[j]>tmp){
                array[j+gap]=array[j];
            }else{
                break;
            }    
            j-=gap;
        }
        array[j+gap]=tmp;
    }
}

3.性质

稳定性：不稳定

时间复杂度：gap取值方式多样希尔排序时间复杂度很难计算但因为gap是按照Knuth提出的取值方式而且Knuth进行了大量的实验统计因此时间复杂度暂定为O(n^1.25)~O(1.6*n^1.25)。

注：希尔排序是对直接插入排序的优化；当gap>1时都是预排序目的是让数组更接近于有序。当gap=1时数组已经接近于有序所以完成排序会很快。

三、选择排序

1、定义

每次从待排序的数据中选出最小的一个元素依次存放在序列的起始位置直到待排元素全部排完。

2、直接选择排序

1.操作

在待排元素集合中选取一个最小的元素。
如果该元素不是这组元素中的第一个元素则将它与第一个元素交换位置。
在剩下的元素集合中arr[i+1]~arr[n-1]中重复以上过程直到集合剩余一个元素

2.代码

public static void selectSort(int[] array){
    for(int i=0;i<array.length;i++){
        int minIndex=i;
        int j=i+1;
        while(j<array.length){
            if(array[j]<array[minIndex]){
                minIndex=j;
            }
            j++;
        }
        swap(array,i,minIndex);
    }
}

3.性质

稳定性：不稳定
时间复杂度：O(N^2)
空间复杂度：O(1)

注：直接选择排序效率不是很好实际中很少用到。

3、堆排序

堆排序是利用堆积树这种数据结构的一种排序算法是通过堆来进行数据选择排升序建大堆排降序建小堆

1.操作

以升序为例先用集合元素建一个堆然后通过向下调整将最大的数放到顶部其次将顶部元素与最后一个元素互换并且usedSize-1再次重复以上过程直到usedSize=1时完成排序。

2.代码

public static void heapSort(int[] array){
    creatBigHeap(array);
    int end=usedSize-1;
    while(end>0){
        swap(array,0,end);
        shiftDown(array,0,end);
        end--;
    }
}
public static void createBigSort(int[] array){
    for(int parent=(array.length-1-1)/2;parent>=0;parent--){
        shiftDown(array,parent,array.length);
    }
}
public static void shiftDown(int[] array,int parent,int len){
    int child=parent*2+1;
    while(child<len){
        if(child+1<len&&array[child]<array[child+1]){
            child++;
        }
        if(array[child]>array[parent]){
            swap(array,child,parent);
            parent=child;
            child=parent*2+1;
        }else{
            break;
        }
    }
}

3.性质

稳定性：不稳定
时间复杂度：O(N*logN)
空间复杂度：O(1)

四、交换排序

1、定义

将值较大的元素向尾部移将值较小的元素向头部移

2、冒泡排序

1.操作

从一堆元素中找到最大的一个然后放到尾部再在剩下的集合中重复以上过程直到集合剩下一个元素时完成排序。

2.代码

public static void bubbleSort(int[] array){
    for(int i=0;i<array.length-1;i++){
        boolean flag=true;
        for(int j=0;j<array.length-1-i;j++){
            if(array[j]>array[j+1]){
                swap(array,j,j+1);
                flag=false;
            }
        }
        if(flag){
            return;
        }
    }
}

3.性质

稳定性：稳定
时间复杂度：O(N^2)
空间复杂度：O(1)

3、快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法

1.操作

任取待排序元素集合中的某个元素作为基准值按照该基准值将集合分割成两个子序列左子序列中的所有元素均小于该基准值右序列中的所有元素均大于该基准值然后左右子序列重复以上过程直到完成排序。

2.代码

public static void quickSort(int[] array){
    quick(array,0,array.length-1);
}
public static void quick(int[] array,int start,int end){
    if(start>=end){
        return;
    }
    int pivot=partition(array,start,end);
    quick(array,start,pivot-1);
    quick(array,pivot+1;end);
}

【1】.Hoare法

public static int partition(int[] array,int left,int right){
    int tmp=array[left];
    int i=left;
    while(left<right){
        while(left<right&&array[right]>=tmp){
            right--;
        }
        while(left<right&&array[left]<=tmp){
             left++;   
        }
        swap(array,left,right);
    }
    swap(array,i,left);
    return left;
}

【2】.挖坑法

public static int partition(int[] array,int left,int right){
    int tmp=array[left];
    while(left<right){  
        while(left<right&&array[right]>=tmp){
            right--;
        }    
        array[left]=array[right];
        while(left<right&&array[left]<=tmp){
            left++;
        }
        array[right]=array[left];
    }
    array[left]=tmp;
    return left;
}

【3】.前后指针法

public static int partition(int[] array,int left,int right){
    int prev=left;
    int cur=left+1;
    while(cur<=right){
        if(array[cur]<array[left]&&array[++prev]!=array[cur]){
            swap(array,cur,prev);
        }
        cur++;
    }        
    swap(array,prev,left);
    return prev;
}

4.性质

稳定性：不稳定
时间复杂度：O(N*logN)
空间复杂度：O(logN)

5.优化快速排序

【1】.三数取中法选取key

private static int midThree(int[] array,int left,int right){
    int mid=(left+right)/2;
    if(array[left]<array[right]){
        if(array[mid]<array[left]){
            return left;
        } else if (array[mid]>array[right]) {
            return right;
        }else{
            return mid;
        }
    }else{
        if(array[mid]<array[right]){
            return right;
        }else if(array[mid]>array[left]){
            return left;
        }else {
            return mid;
        }
    }
}

【2】.递归到小的子区间时使用插入排序

public static void quick(int[] array,int start,int end){
	if(start>=end){
		return;
	}
	//使用这个优化主要是解决减少递归的次数
	if(end-start+1<=14){
		//插入排序
		insertSort2(array,start,end);
		return;
	}
	//三数取中法
	int index=midThree(array,start,end);
	swap(array,index,start);
	int pivot=partition(array,start,end);
	quick(array,start,pivot-1);
	quick(array,pivot+1,end);
}

6.非递归实现快速排序

public static quickSort2(int[] array){
    Deque<Integer> stack=new LinkedList<>();
    int left=0;
    int right=array.length-1;
    int pivot=partition(array,left,right);
    if(pivot>left+1){
        stack.push(left);
        stack.push(pivot-1);
    }
    if(pivot<right-1){
        stack.push(pivot+1);
        stack.push(right);
    }
    while(!stack.isEmpty()){
        right=stack.pop();
        left=stack.pop();
        pivot=partition(array,left,right);
        if(pivot>left+1){
            stack.push(left);
            stack.push(pivot-1);
        }
        if(pivot<right-1){
            stack.push(pivot+1);
            stack.push(right);
        }
    }    
}

五、归并排序

1、定义

归并排序是建立在归并操作上的一种排序算法该算法采用的是分治法。

2、操作

先将序列分解成多个单数子序列再将子序列合并成有序序列将两个有序表合并成一个有序表称为二路归并。

3、代码

public static void mergeSort(int[] array){
    mergeSortFunc(array,0,array.length-1);
}
public static void mergeSortFunc(int[] array,int left,int right){
    if(left>=right){
        return;
    }
    int mid=(left+right)/2;
    mergeSortFunc(array,left,mid);
    mergeSortFunc(array,mid+1,right);
    merge(array,left,right,mid);
}
public static void merge(int[] array,int start,int end,int mid){
    int s1=start;
    int s2=mid+1;
    int[] tmp=new int[end-start+1];
    int k=0;
    while(s1<=mid&&s2<=end){
        if(array[s1]<=array[s2]){
            tmp[k++]=array[s1++];
        }else{
            tmp[k++]=array[s2++];
        }
    }
    while(s1<=mid){
        tmp[k++]=array[s1++];
    }
    while(s2<=end){
        tmp[k++]=array[s2++];
    }
    for(int i=0;i<tmp.length;i++){
        array[i+start]=tmp[i];
    }
}

4、性质

稳定性：稳定
时间复杂度：O(N*logN)
空间复杂度：O(N)

注：归并排序的缺点在于需要O(N)的空间复杂度归并排序更多是用来解决磁盘中的外排序问题。在大量数据的排序中内存无法将所有数据全部放下所以需要外部排序而归并排序就是最常用的外部排序

5、非递归的归并排序

public static void mergeSort2(int[] array){
	int gap=1;
	while(gap<array.length){
		// i += gap * 2 当前gap组的时候去排序下一组
		for(int i=0;i<array.length;i+=gap*2){
			int left=i;
			int mid=left+gap-1;
			if(mid>=array.length){
				mid=array.length-1;
			}
			int right=mid+gap;
			if(right>=array.length){
				right=array.length-1;
			}
			merge(array,left,right,mid);
		}
		//当前为2组有序  下次变成4组有序
		gap*=2;
	}
}

六、常见排序算法复杂度及稳定性

排序方法	最好	平均	最坏	空间复杂度	稳定性
冒泡排序	O(N)	O(N^2)	O(N^2)	O(1)	稳定
插入排序	O(N)	O(N^2)	O(N^2)	O(1)	稳定
选择排序	O(N^2)	O(N^2)	O(N^2)	O(1)	不稳定
希尔排序	O(N)	O(N^1.3)	O(N^2)	O(1)	不稳定
堆排序	O(N*logN)	O(N*logN)	O(N*logN)	O(1)	不稳定
快速排序	O(N*logN)	O(N*logN)	O(N^2)	O(logN)~O(N)	不稳定
归并排序	O(N*logN)	O(N*logN)	O(N*logN)	O(N)	稳定

七、其他非基于比较排序

1、计数排序

计数排序又称为鸽巢原理是对哈希直接定址法的变形应用

1.操作

统计相同元素出现的次数
根据统计的结果将序列回收到原来的序列中

2.代码

public static void countSort(int[] array){
    //找到数组中的最大值和最小值
    int max=array[0];
    int min=array[0];
    for(int i=1;i<array.length;i++){
        if(array[i]<min){
            min=array[i];
        }    
        if(array[i]>max){
            max=array[i];
        }
    }
    //根据范围定义计数数组的长度
    int len=max-min+1;
    int[] count=new int[len];
    //遍历数组在计数数组中记录每个数字出现的次数
    for(int i=0;i<array.length;i++){
        count[array[i]-min]++;
    }
    //遍历计数数组
    int index=0;
    for(int i=0;i<count.length;i++){
        while(count[i]>0){
            array[index]=i+min;
            index++;
            count[i]--;
        }
    }
}