数据结构-排序部分
了解排序
排序: 所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或者递减排列起来的操作.
稳定性: 在一组元素中可能存在相等的元素,如果经过排序,这些记录的相对次序保持不变,那么认为这种排序是稳定的,否则是不稳定的.
在排序的过程中如果没有间隔交换或者插入,则该种排序算法都是稳定的.
如下图所示.
排序分类
1.插入排序
基本思想:
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列.
现实中的例子:
我们在玩扑克牌的时候,手里的牌是排好序的,当我们摸上来一张牌的时候,就需要把这张牌插入到相应的位置,这就是插入排序.
1.1 直接插入排序
算法思想:
当插入第i个元素时,前面的元素已经排好序了,然后用这个元素和前面的元素依次进行比较,如果找到插入位置,将元素插入,然后将此位置后面的元素依次往后移动.
算法动图演示:
后面的元素依次与前面的元素进行比较,如果小于前面元素,则插入到前面,否则不动.
来举一个简单的小例子.
如图,我们现在要往下面的序列中插入元素3
算法实现步骤:
a.找待插入元素的位置
用end指针标记序列最后一个元素,用key和end位置元素比较,如果 end>=0 && key<array[end] 时,将end位置元素后移一位,然后end- -,直到找到相应的位置.
注意:这里的end>=0原因是,如果我们要往当前的例子中插入元素0的话,在最后一步中end- -后就成了负数,会报数组下标越界异常,所以要加一个判断条件.
代码实现:
while(end>=0 && key<array[end]){
array[end+1]=array[end];
end--;
}
图形演示:
end- -以后,key的值(3)大于此时end位置的值(2),所以已经找到了该插入的位置.
b.将元素插入到end+1的位置
从步骤a中可以知道,在找到位置后,end的位置在该插入位置之前的一个单位,所以将key插入到end+1的位置.
代码实现:
array[end+1]=key;
图形演示:
在这里,这个例子就已经讲完了.
但是在实际排序中,整个序列都不一定有序,所以我们一般默认第一个位置元素已经排好序了,然后将这个元素后面的每个元素依次插入到相应的位置.
代码实现如下:
public class InsertSort {
//打印数组的方法
static void printArray(int[] array){
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]+" ");
}
System.out.println();
}
public static void main(String[] args) {
//一个无序的序列.
int[] array={7,6,5,8,1,3,9,2,4,0};
for (int i = 1; i < array.length; i++) {
//此时我们认为有序的只有7,所以用end标记有序序列的最后一个元素.
//然后将7后面的元素依次进行插入排序.
int end=i-1;
int key=array[i];
while (end>=0 && key<array[end]){
array[end+1]=array[end];
end--;
}
array[end+1]=key;
}
//打印数组.
printArray(array);
}
}
直接排序算法特性总结:
1.元素集合越接近有序,直接插入排序算法的时间效率越高.
2.时间复杂度(取最坏的情况): O(N^2),最佳的情况为O(N).
3.空间复杂度:O(1),它是一种稳定的排序算法.
4.稳定性:稳定.(大家可以自己想一个例子进行证明)
5.应用场景数据接近有序或者数据量比较小的情况.
1.2 希尔排序(也可以说是插入排序PLUS)
基本思想:
利用分组的方式将数据量降下来,然后对每一组的数据进行插入排序.
算法动图演示:
举例进行解释说明:
先给定一个数据序列:{7,6,5,8,1,3,9,2,4,0}.然后对这个序列进行希尔排序.
1.当gap=10的时候,按照间隔为10分组,就相当没有分组,还是原来的序列.
2.当gap=gap/2=5的时候.按照间隔为5进行分组,然后对每个组进行插入排序
数字颜色相同的在一个组
3.当gap=gap/2=2的时候.按照间隔为2进行分组,然后对每个组进行插入排序
数字颜色相同的在一个组
4.当gap=gap/2=1的时候.按照间隔为1进行分组,也就是对这个数组直接进行插入排序
我们用一个上面的第3步来对代码进行一个简单的解释.(gap=2)
a.刚开始i等于gap,标记下标为gap位置的元素.
b.用end标记当前分组的前一个元素,也就是i-gap位置的元素int end=i-gap;
key记录此时要插入的元素int key=array[i];
c.如果end>=0 && key<array[end],将end位置元素后移gap位,然后end-=gap直到找到合适的位置.其实和插入排序一样,只不过这里的单位间隔是gap不是插入排序默认的1.执行完后i++;进入下一个组中进行插入排序.让这个步骤循环起来.
代码展示:
for (int i = gap; i < size; i++) {
int end=i-gap;
int key=array[i];
while (end>=0 && key<array[end]){
array[end+gap]=array[end];
end-=gap;
}
array[end+gap]=key;
}
图形理解:
代码实现如下:
public class ShellSort {
//打印数组的方法
static void printArray(int[] array){
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]+" ");
}
System.out.println();
}
public static void main(String[] args) {
int[] array={7,6,5,8,1,3,9,2,4,0};
int size=array.length;
//让gap刚开始等于数组长度.
int gap=size;
while (gap>0){
//将元素插入数组中
//array数组中:[0,i)的元素已经排好序了.
//i位置的数据是本次要插入的数据
for (int i = gap; i < size; i++) {
//这里的i++就相当于去排另外一个组里面的元素了.
//下方的代码就是对插入排序进行一个简单的修改.
int end=i-gap;
int key=array[i];
while (end>=0 && key<array[end]){
array[end+gap]=array[end];
end-=gap;
}
array[end+gap]=key;
}
//当前分组排序完成后,进行下次新的分组排序.
gap/=2;
}
//打印数组
printArray(array);
}
}
希尔排序的特性总结:
1.希尔排序是对直接插入排序的优化
2.当gap>1时,都是预排序,目的是让数组更加的接近有序.当gap=1的时候,数组已经非常接近有序的了,这样排序就会很快.整体而言,可以达到优化的效果.
3.希尔排序的时间复杂度不好算,因为gap的取值方法有很多,导致很难去计算,希尔排序的时间复杂度不是固定的.因为我们这里是按照Knuth提出的方式进行取值的,而且Knuth进行了大量的实验进行证明统计.所以我们暂时就按照O(n ^ 1.25)到O(1.6 * N^1.25)来算.
4.空间复杂度O(1)
5.稳定性:不稳定.
2.选择排序
基本思想:
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完.
2.1 直接选择排序
基本思想:
在序列中找最小元素(最大元素)的位置,然后将该元素与区间第一个元素(最后一个元素)进行交换.
算法动图演示:
给定一个序列:{7,6,5,8,1,3,9,2,4,0},进行选择排序.这里我们进行升序排列,所以是找最大的元素进行排列.
算法实现步骤:
找到最大元素的位置,然后将该元素与区间最后一个元素进行交换.
图形理解:
第一趟查找
第二趟查找:
此时9已经排好序了,所以和9前面的元素进行交换.就这样一直查找并交换,最后会排列成升序序列.
代码实现如下:
public class SelectSort {
//打印数组的方法
static void printArray(int[] array){
for (int i = 0; i <array.length ; i++) {
System.out.print(array[i]+" ");
}
}
//交换数据的方法
static void swap(int[] array,int left,int right){
int temp=array[left];
array[left]=array[right];
array[right]=temp;
}
public static void main(String[] args) {
int[] array={7,6,5,8,1,3,9,2,4,0};
//控制选择的趟数
for(int i=0;i<array.length;i++){
//刚开始时让pos默认去标记第一个元素的位置.
int pos=0;
//然后用一个for循环去找最大的元素位置
//arr.length-i的原因是排好后,最后一个元素就不用动了,肯定是最大的.
for (int j = 0; j < array.length-i; j++) {
//当j下标位置的元素大于pos位置的元素时,用pos记录当前j的位置.
//最后循环结束时,pos标记的就是最大元素位置.
if(array[j]>array[pos]){
//此时的pos标记的就是最大元素位置
pos=j;
}
}
//将该位置上的元素与区间最后一个元素进行交换.
//判断的原因是:如果最大的元素本来就在末尾位置,那么就不需要交换了.
if (pos != array.length-1-i){
//交换的方法.
swap(array,pos,array.length-i-1);
}
}
//打印数组
printArray(array);
}
}
特别篇: 直接选择排序的优化
基本思想:
用minPos标记最小元素位置,maxPos标记最大元素位置.begin标记区间最左侧元素,end标记区间最右侧元素.
用minPos位置元素与begin位置元素进行交换,maxPos位置元素与end位置元素进行交换.
算法实现步骤:
a.刚开始让minPos和maxPos都指向最左侧位置.
b.用一个索引index去找最大和最小的元素.index从begin+1开始
c.当index位置的元素大于begin位置的元素时,用maxPox标记当前位置.
当index位置的元素小于begin位置的元素时,用minPox标记当前位置.
直到找到最大的元素和最小的元素.
d.用minPos位置的元素和begin位置的元素进行交换,
用maxPos位置的元素和end位置的元素进行交换.
然后begin++;end--;
第一趟查找交换
第二趟查找交换
后面的步骤就依次类推就行.
代码实现如下:
public class SelectSortPlus {
//打印数组的方法
static void printArray(int[] array){
for (int i = 0; i <array.length ; i++) {
System.out.print(array[i]+" ");
}
}
//交换函数的方法
static void swap(int[] array,int left,int right){
int temp=array[left];
array[left]=array[right];
array[right]=temp;
}
public static void main(String[] args) {
int[] array={7,6,5,8,1,3,9,2,4,0};
//让end刚开始处在第一个元素位置
int begin=0;
//end处在末尾元素位置.
int end=array.length-1;
while (begin < end){
//默认minPos,maxPos,index的设置
int minPos=begin;
int maxPos=begin;
int index=begin+1;
//当index<=end的时候,说明还存在元素没有比较完.
while (index <= end){
//如果index位置元素大于maxPos位置元素,则用maxPos标记此时index的位置
if (array[index]>array[maxPos]){
maxPos=index;
}
//如果index位置元素小于maxPos位置元素,则用minPos标记此时index的位置
if (array[index]<array[minPos]){
minPos=index;
}
//index往后移动,依次遍历
index++;
}
//如果maxPos没有处在末尾,则进行值的交换
if (maxPos!=end){
//调用交换方法
swap(array,maxPos,end);
}
//如果minPos处在end的位置,则用minPos标记maxPos的位置.
//具体的解释在上面图中.
if (minPos==end){
minPos=maxPos;
}
//如果minPos不在begin的的位置,则进行值的交换
if (minPos!=begin){
//调用交换方法
swap(array,minPos,begin);
}
//begin后移一位,end前移一位.
begin++;
end--;
}
//打印数组.
printArray(array);
}
}
直接选择排序的特性总结:
1.好理解,但是效率不是很好,实际中很少使用.
2.时间复杂度:O(N^2)
3.空间复杂度:O(1)
4.稳定性:不稳定.
2.2 堆排序
想要了解清楚这一部分内容,就要对堆有一个理解.
不熟悉的兄弟们可以点击传送门去了解了解.
传送门:优先级队列(堆)
大家直接去看堆的创建部分就行.有完整的图形解释.
基本思想:
堆排序(Heapsort)是指利用（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。
需要注意的是排升序要建大堆，排降序建小堆。
算法实现步骤:
1.建堆(需要用到向下调整)------>升序建大堆,降序建小堆.
a.找倒数第一个非叶子节点:(size-1-1)/2
b.从倒数第一个非叶子的位置倒着往根的方向走:遇到每个节点,将该节点向下调整
2.利用堆删除的思想来进行排序
a.用堆顶的元素和堆中最后一个元素进行交换.就是将最大的元素放在了最后的位置.所以要建大堆
b.将堆中有效元素个数减少一个,最大的值就不用动了.
c.将堆顶元素向下调整
代码实现如下:
public class HeapSort {
static void printArray(int[] array){
for (int i = 0; i <array.length ; i++) {
System.out.print(array[i]+" ");
}
}
static void swap(int[] array,int left,int right){
int temp=array[left];
array[left]=array[right];
array[right]=temp;
}
//向下调整方法建大堆
static void shiftDown(int[] array,int size,int parent){
//默认为左孩子
int child=parent*2+1;
while (child<size){
//在这里对右孩子也进行范围判断.如果child+1>size的话会数组小标越界.
if (child+1<size && array[child+1]>array[child]){
//如果右孩子>左孩子,将child下标放在右孩子位置.
child+=1;
}
//如果parent处的值小于child处的值,则进行交换.让大的值往下走.
if (array[parent]<array[child]){
swap(array,parent,child);
//交换完后,将parent放在child位置,再让child放在当前parent的左孩子位置.
parent=child;
child=parent*2+1;
}else{
return;
}
}
}
public static void main(String[] args) {
int[] array={7,6,5,8,1,3,9,2,4,0};
int size=array.length;
//建堆,从倒数第一个非叶子节点开始
int lastLeaf=(size-2)/2;
for (int root=lastLeaf; root >=0; root--) {
//向下调整建大堆,因为我们需要升序序列
//此时的size为array.length
shiftDown(array,size,root);
}
//因为size是数组长度,所以数据不能交换放到array[size]的位置.
//所以end=size-1.
int end=size-1;
while (end>0){
//将堆顶的元素交换到数组末尾位置.
swap(array,0,end);
//继续向下调整剩下的元素.
shiftDown(array,end,0);
//堆顶元素交换完成后就不需要动了,所以end要--,
end--;
}
printArray(array);
}
}
堆排序的特性总结:
1.堆排序使用堆来选数，效率就高了很多。
2.时间复杂度：O(N*logN)
3.空间复杂度：O(1)
4.稳定性：不稳定
3.交换排序
基本思想:
根据序列中两个元素值的比较结果来对换这两个记录在序列中的位置.
交换排序的特点是:
将值大的元素往序列的尾部移动,序列小的元素往序列的前部移动.
3.1 冒泡排序
基本思想:
通过比较相邻的两个元素,根据结果将两个元素的位置互换.
如果想要升序的话就小元素前移,大元素后移.降序则相反.
假如相邻的两个元素是6,4,那么通过比较,6>4,所以两个元素要互换位置,变成4,6.
算法动图演示:
我们还是直接上例子:
给定一个序列:{7,6,5,8,1,3,9,2,4,0},进行冒泡排序.这里我们进行升序排列,所以小元素前移,大元素后移.
算法实现步骤:
两层循环,外层循环控制趟数,内层循环进行遍历比较
a.初始令j=1,标记下标为1的元素,与前一个元素(j-1)位置元素进行比较.
b.如果当前元素小于前一个元素就交换位置,大于前一个元素的话j++,再次进行比较.
if (arr[j-1]>arr[j]){
int temp=arr[j-1];
arr[j-1]=arr[j];
arr[j]=temp;
}
用图形理解:
第一趟比较交换:
后面的比较和上面的步骤一样,j又从1开始和j-1位置的元素进行比较交换,只不过这次比较的次数少了一次,因为第一趟中的9已经排好了,就不需要再排一次了
代码实现如下:
public class BubbleSort {
//排序算法
public static void bubbleSort(int[] arr){
//循环遍历的趟数i
for (int i = 0; i <arr.length; i++) {
for (int j = 1; j < arr.length-i; j++) {
/*
比较前一个元素和当前元素
如果前一个元素大于后一个元素,则两元素进行交换.
j++进行数组下标右移,依次进行比较,
这样就会将最大的元素移动到数组最后一个位置
此时i++,实现第二趟元素比较,这个时候,数组的最后一个元素
是最大值不需要比较,所以j<arr.length-i,比较到前一个元素
*/
//我这里使用的是升序排列,如果需要降序排列
//将arr[j-1]>arr[j]改为arr[j-1]<arr[j]就行
if (arr[j-1]>arr[j]){
int temp=arr[j-1];
arr[j-1]=arr[j];
arr[j]=temp;
}
}
}
}
//打印数组的方法
public static void printArray(int[] arr){
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr={6,4,2,5,8,7,1,3,9,0};
//调用排序数组方法
bubbleSort(arr);
//调用遍历打印数组方法
printArray(arr);
}
}
冒泡排序的特性总结:
1.是一种非常好理解的排序算法
2.时间复杂度:O(N^2)
3.空间复杂度:O(1)
4.稳定性:稳定
3.2 快速排序(快排)
基本思想:
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两个子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止.
我们都是假设升序进行代码的实现.
算法步骤:
1.找一个基准值:基准值没有规定一定要去怎么找,区间中任何一个数字都可以作为基准值,但是从代码的可行性上说,一般取的是区间两侧的数据.
2.然后按照基准值将区间分割成两个部分:左侧部分比基准值小,右侧部分比基准值大.
3.递归进左侧再次进行分割,递归进右侧再次进行分割.
4.等递归到区间只剩下一个元素才往回退.
代码:
void QuickSort(int[] array, int left, int right)
{
if(right - left > 1){
// 按照基准值对array数组的 [left, right)区间中的元素进行划分
//partition是分割数据的方法.
int div = partition(array, left, right);
// 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
// 递归排[left, div)
QuickSort(array, left, div);
// 递归排[div+1, right)
QuickSort(array, div+1, right);
}
}
数据分割的方法有三种:Hoare版,挖坑法,前后指针法.
3.2.1 Hoare版
算法动图演示:
来举例解释:
有一个序列为:{4,2,8,6,9,1,3,7,0,5},我们选最右侧的值作为基准值,所以key=5.
算法实现步骤:
此时以基准值5分割数据.
1.用begin标记数组首元素位置,end标记数组末尾元素.
2.begin依次往后走,找到比基准值大的元素就停下来.
3.end往前走,找到比基准值小的元素就停下来.
4.然后将begin和end位置的元素交换一下.
5.然后重复2,3,4步骤,直到begin和end相遇后,将基准值和此位置元素进行交换.
6.将此时基准值的下标返回作为分割依据,也就是此时begin的下标.供递归使用
图形演示:
此时数据被分割为以div为边界的左右两个部分.分别为[left,div),[div+1,right),div是基准值的下标
然后我们递归对div的左侧部分进行分割排序.
图形演示:
就这样一直递归着分割排序,最终得到的就是升序的序列.
代码实现如下:
public class QuickSort1 {
static void printArray(int[] array){
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]+" ");
}
}
static void swap(int[] array,int left,int right){
int temp=array[left];
array[left]=array[right];
array[right]=temp;
}
//分割数据的方法.
static int partition(int[] array,int left,int right){
//默认以数组的最右侧元素作为基准值.
int key=array[right-1];
//begin从数组第一个元素位置开始.
int begin=0;
//end从数组最后一个元素位置开始.
int end=right-1;
//当begin<end时,说明还有元素没有寻找完.
while (begin < end){
//当begin处的元素<=基准值时,begin往后走,直到begin处的元素>基准值时停下.
while (begin < end && array[begin] <= key){
begin++;
}
//当end处的元素>=基准值时,end往前走,直到end处的元素<基准值时停下.
while (begin < end && array[end] >= key){
end--;
}
//如果begin与end没有相遇,交换两个位置的元素值
if (begin!=end){
swap(array,begin,end);
}
}
//如果begin没有在末尾位置,则交换两个位置的元素值
if (begin!=right-1){
swap(array,begin,right-1);
}
//返回此时基准值的下标.
return begin;
}
static void quickSort(int[] array,int left,int right){
if (right-left>1){
//接收返回来的下标将[left,right)区间分割成两个部分
int div=partition(array,left,right);
//递归排左侧部分,比基准值小,[left,div)
quickSort(array,left,div);
//递归排右侧部分,比基准值大,[div+1,right)
quickSort(array,div+1,right);
}
}
public static void main(String[] args) {
int[] array={7,6,5,8,1,3,9,2,4,0};
quickSort(array,0,array.length);
printArray(array);
}
}
3.2.2 挖坑法
算法动图演示:
来举例解释:
有一个序列为:{4,2,8,6,9,1,3,7,0,5},我们选最右侧的值作为基准值,所以key=5.
算法实现步骤:
以基准值5分割数据
1.用一个中间变量保存基准值,所以我们可以认为基准值被挖走了,所以它的位置就空出来了.
2.用begin标记数组首元素位置,end标记数组末尾元素.
3.begin依次往后走,找到比基准值大的元素就去填上一个坑.此时begin的位置就成为了一个新坑.
4.end往前走,找到比基准值小的元素就填上一个坑.此时end的位置就成为了一个新坑.
5.然后重复3,4步骤,直到begin和end相遇后,用基准值将此位置的坑一补.
6.将此时基准值的下标返回作为分割依据,也就是此时begin的下标.供递归使用
图形演示:
此时数据被分割为以div为边界的左右两个部分.分别为[left,div),[div+1,right),div是基准值的下标.
然后对左右两侧进行递归就行.
代码实现如下:
public class QuickSort2 {
static void printArray(int[] array){
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]+" ");
}
}
static void swap(int[] array,int left,int right){
int temp=array[left];
array[left]=array[right];
array[right]=temp;
}
//分割数据的方法
static int partition(int[] array,int left,int right){
//默认以数组最右侧的数据作为返回值.
int key=array[right-1];
//begin从数组第一个元素位置开始.
int begin=left;
//end从数组最后一个元素的位置开始
int end=right-1;
//当begin<end时,说明还有元素没有寻找完.
while (begin <end){
//当begin处的元素<=key的值时,begin往后走
while (begin<end && array[begin]<=key){
begin++;
}
//当begin位置的元素大于key的值时,用begin位置的元素去覆盖end位置的元素
//也就是所谓的填上一个坑,此时begin的位置就形成了一个新坑
if (begin<end){
array[end]=array[begin];
}
//当end位置的元素<=key的值时,end往前走
while (begin<end && array[end]>=key){
end--;
}
//当end位置的元素小于key的值时,用end位置的元素去覆盖begin位置的元素
//也就时去填上一个坑,此时end的位置就形成了一个新坑
if (begin<end){
array[begin]=array[end];
}
}
//两者相遇的时候,将key的值放入坑的位置.
array[begin]=key;
//返回此时基准值的下标,
return begin;
}
static void quickSort(int[] array,int left,int right){
if (right-left>1){
//接收返回来的下标将[left,right)区间分割成两个部分
int div=partition(array,left,right);
//递归排左侧部分,比基准值小,[left,div)
quickSort(array,left,div);
//递归排右侧部分,比基准值大,[div+1,right)
quickSort(array,div+1,right);
}
}
public static void main(String[] args) {
int[] array={7,6,5,8,1,3,9,2,4,0};
quickSort(array,0,array.length);
printArray(array);
}
}
3.2.3 前后指针法(不太好想,大家掌握前两种就行了)
来举例解释:
有一个序列为:{4,2,8,6,9,1,3,7,0,5},我们选最右侧的值作为基准值,所以key=5.
算法实现步骤:
1.left表示数组的左边界,用cur保存一份,用prev表示cur的前一个元素.
int cur = left;int prev=cur-1;
2.right表示数组的右边界,如果array[cur]<key&& ++prev!=cur,就交换prev和cur处的值.不管是否满足条件,cur都往后走一步.
注意:此处是++prev,即是prev+1后再执行语句.
3.两个条件都满足时,交换两个位置的元素,cur继续后移.
4.当array[cur]=key时,cur=right跳出循环,此时判断prev++!=right-1,所以交换prev位置元素和right-1位置元素.返回此时prev的下标,作为下一次分割依据
代码:
int cur=left;
int prev=cur-1;
int key=array[right-1];
while (cur<right){
if (array[cur]<key && ++prev != cur){
swap(array,cur,prev);
}
cur++;
}
if (++prev!=right-1){
swap(array,prev,right-1);
}
return prev;
图形演示:
此时原来的数据就会被分割成两部分,再经过递归后就可以将数据分割排序.
代码实现如下:
public class QuickSort3 {
static void printArray(int[] array){
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]+" ");
}
}
static void swap(int[] array,int left,int right){
int temp=array[left];
array[left]=array[right];
array[right]=temp;
}
static int partition(int[] array,int left,int right){
//cur是数组第一个元素下标
int cur=left;
//prev初始时是cur的前一个元素下标
int prev=cur-1;
//基准值key初始时是数组最后一个元素.
int key=array[right-1];
//当cur<right时,说明数组中的元素还没有寻找完.
while (cur<right){
//满足此条件的话,交换prev和cur处的值
if (array[cur]<key && ++prev != cur){
swap(array,cur,prev);
}
//不管是否满足上面if中的条件,cur都要往后走一步.
cur++;
}
//能走到这一步,就说明数组中的元素都找完了
//当prev+1后没有处于末尾的位置,就交换两位置的元素
if (++prev!=right-1){
swap(array,prev,right-1);
}
//然后返回此时基准值的下标.
return prev;
}
static void quickSort(int[] array,int left,int right){
if (right-left>1){
int div=partition(array,left,right);
quickSort(array,left,div);
quickSort(array,div+1,right);
}
}
public static void main(String[] args) {
int[] array={7,6,5,8,1,3,9,2,4,0};
quickSort(array,0,array.length);
printArray(array);
}
}
快排性能分析:
最坏场景:
如果序列有序或者接近有序,每次取到基准值如果是区间中的最大值或者最小值,那么基准值就会出现一侧有数据,一侧没有数据.因此快排不适合于有序或者接近有序的场景进行排序.
时间复杂度:O(N^2)
最优场景:
序列比较随机,数据比较凌乱:每次取基准值都比较理想.
时间复杂度:O(N*logN)
应用场景: 数据非常随机,数据非常凌乱
在这里要注意,快排一般给的时间复杂度都是O(N*logN)而不是O(N^2),所以要避免去取到极值的概率.
快速排序的特性总结:
1.快速排序整体的综合性能和使用前景都是比较好的,所以才敢叫快速排序.
2.时间复杂度:O(N*logN)
3.空间复杂度:O(logN)
4.稳定性:不稳定.
3.2.4 快速排序的优化
之前取极值的方法为了代码实现的方便,我们是从区间的最左侧或者最右侧取基准值,但是从两侧取值取到极值的概率会非常高.
所以我们要重新找一个取极值的方法.
三数取中法—>一次性取三个数: 最左侧取一个数据,最右侧取一个数据,中间再取一个数据,以这三个数据最中间的数据作为基准值.
算法实现步骤:
1.left标记数组最左侧元素,right是数组长度.mid标记中间元素.
2.三个元素进行比较,如果 array[mid]<左<右,所以left标记的是中间元素,返回left
3.如果 左<右<array[mid],(right-1)标记的是中间元素,返回(right-1).
4.如果 左<array[mid]<右,mid标记的是中间元素,返回mid.
代码实现如下:
//这个方法就相当于比较三个数的大小,然后返回处于中间的那一个数的下标.
//
static int getIndexOfMiddle(int[] array,int left,int right){
int mid=left+(right-left)/2;
if(array[left]<array[right-1]){
if(array[mid]<array[left]){
return left;
}else if(array[mid]>array[right-1]){
return right-1;
}else{
return mid;
}
}else{
if(array[mid]>array[left]){
return left;
}else if(array[mid]<array[right]){
return right-1;
}else{
return mid;
}
}
}
接下来就是将这块代码和上面分割的方法结合起来,我就直接用一下上面Hoare版的例子进行结合说明.
结合完的代码如下:
static int partition(int[] array,int left,int right){
//接收这个方法返回来的中间元素下标.
int index=getIndexOfMiddle(array,left,right);
if(index!=right-1){
//如果index没有在末尾的时候,将两个元素位置互换
//这样就不用去改变下方的代码了
swap(array,index,right-1);
}
int key=array[right-1];
int begin=left;
int end=right-1;
while (begin < end){
while (begin < end && array[begin] <= key){
begin++;
}
while (begin < end && array[end] >= key){
end--;
}
if (begin!=end){
swap(array,begin,end);
}
}
if (begin!=right-1){
swap(array,begin,right-1);
}
return begin;
}
3.2.5 快排的非递归算法(这个大家了解一下就行)
在这里我们用到了栈.用栈来存储左右区间.
做法:
1.先将初始数组的左右边界,array.length,0入栈,这是分割前的第一个区间.
2.当栈不为空时,说明栈中还有区间,将数据出栈,注意是 先入后出,所以将左边界给left,右边界给right.
3.当right-left>1时,将区间[left,right)以下标div进行分割.然后将右侧区间[div+1,right)进行入栈,再将左侧区间[left,div)进行入栈.
下一次出栈时,会让left和div出栈再次进行分割后再入栈.大家可以根据代码自己模拟画一下接下来的图形.
注意:一定要先入每个区间的右侧位置.因为这是栈,是先入后出的.
4.让2,3步骤循环起来,直到栈为空.
代码实现如下:
void QuickSortNonR(int[] a, int left, int right){
Stack<Integer> st = new Stack<>();
//先开始初始情况的入栈
st.push(array.length);
st.push(0);
while (!st.empty())
{
left= st.pop();
right = st.pop();
if(right - left <= 1){
continue;
}
// 以基准值为分割点，形成左右两部分：[left, div) 和 [div+1, right)
int div = partition(a, left, right);
//先将右侧区间进行入栈
st.push(div+1);
st.push(right);
//再将左侧区间进行入栈
st.push(left);
st.push(div);
}
}
4.归并排序
基本思想: 是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用.将已经有序的子序列合并得到完全有序的序列;即先使每个子序列有序,再使子序列段之间有序.
归并排序动图演示:
归并排序的核心步骤如下:
每次对序列进行均分,均分到一定程度,发现区间中的数据有序了,再来进行合并.
分解一个序列就是上方的上半部分图形,进行均分:
原本的序列为 {7,6,5,8,1,3,9,2,4,0},有10个元素.
1.left初值为0,right初值为数组的长度,所以区间为[0,10),
mid=left+(right-left)/2
2.第一次进行均分后,mid为5.左区间为[0,5)右区间为[5,10).
3.递归进去对左区间[0,5)再次进行均分,此时的区间划分为:
一直进行递归划分,就可以得到上面的那个分解阶段的图形.
当分解完成后我们如何将两个有序的序列合并成一个序列呢?
我们就用上述的某个序列,将他们合并成一个新的有序序列进行讲解.
序列1:{1,5,6,7,8},序列2;{0,2,3,4,9},此时的划分mid应该是5,所以左区间为[0,5),右区间为[5,10).
做法步骤:
1.用begin1,begin2,标记这两个序列的初始位置,用index标记新序列的初始位置
2.如果begin1处的元素大于begin2位置的元素,则将begin1处位置的元素搬移到index的位置,然后,begin1++,index++;
3.如果begin1处的元素小于begin2位置的元素,则将begin2处位置的元素搬移到index的位置,然后,begin2++,index++;
4.当某个序列的元素全部搬移完的话,进行判断看另外一个序列中是否还有元素,如果有的话相应往下搬移就行.
图形演示:
初始的时候:
第一次比较:
第二次比较:
第三次比较:
第四次比较:
第五次比较:
中间步骤省略,直接快进到最后8和9进行相比:
到这一步我们会发现,下标begin1已经超出了数组边界,我们通过判断后发现另外一个序列中还有元素,所以将另外一个序列中的元素搬移下来就行,
还有些具体的解释在下面代码中会进行指出.
代码实现如下:
public class MergeSort {
//打印数组的方法
static void printArray(int[] array){
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]+" ");
}
System.out.println();
}
//将序列归并起来排序的算法
static void mergeData(int[] array, int left, int mid, int right, int[] temp){
//begin1标记左侧区间中的首元素,end1标左侧区间的末尾位置.
int begin1=left,end1=mid;
//begin2标记右侧区间中的首元素,end2标右侧区间的末尾位置
int begin2=mid,end2=right;
//index是辅助数组temp的首元素下标.
int index=left;
//左右区间都有元素.
while (begin1<end1 && begin2<end2){
//将满足条件的元素搬移到辅助数组temp中.
if (array[begin1]<=array[begin2]){
temp[index]=array[begin1];
index++;
begin1++;
}else{
temp[index]=array[begin2];
index++;
begin2++;
}
}
//当一个数组搬移完后进行判断另外一个数组中是否还有元素,有的话直接搬移.
while (begin1<end1){
temp[index]=array[begin1];
index++;
begin1++;
}
while (begin2<end2){
temp[index]=array[begin2];
index++;
begin2++;
}
}
//归并排序算法.array是需要排序的数组,left是左边界,right是右边界,temp是辅助空间
private static void mergeSort(int[] array,int left,int right,int[] temp){
if (right-left>1){
//先对[left,right)区间中的元素进行均分,mid是划分依据
int mid=left+(right-left)/2;
//递归对区间[left,mid)区间中的元素进行均分
mergeSort(array,left,mid,temp);
//递归对区间[mid,right]区间中的元素进行均分
mergeSort(array,mid,right,temp);
//将分解开的序列进行归并排序.
//left是左边界,right是右边界,mid是划分依据.
mergeData(array,left,mid,right,temp);
//将temp数组中从索引为left开始,长度为right-left的数据复制到array中，并从索引为left开始。
System.arraycopy(temp,left,array,left,right-left);
}
}
//方法的重载,这样用户在调用的时候就不需要传入多余的数据,只需要传入一个数组就行.
static void mergeSort(int[] array){
int[] temp=new int[array.length];
mergeSort(array,0,array.length,temp);
}
public static void main(String[] args) {
int[] array={7,6,5,8,1,3,9,2,4,0};
//传入这个数组
mergeSort(array);
//打印排好序的数组
printArray(array);
}
}
归并排序的特性总结:
1.归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘外的外排序问题.
2.时间复杂度:O(N*logN)
3.空间复杂度:O(N)
4.稳定性:稳定
5.计数排序
基本思想:
先统计每个元素出现的次数,然后根据计数的结果对数据进行回收
算法实现步骤:
1.通过遍历先去找序列中的最大值(
maxValue)和最小值(minValue),去确定数据的范围(range=maxValue-minValue+1)
2.创建一个长度为range的数组去统计array中每个数据出现的次数.
3.根据统计的结果去回收数据
我们给一组序列 {4,2,3,9,4,7,0,1,1,9,8,2,5,6,4,3}
图形演示:
1.通过计算,range=9-0+1=10,所以我们需要创建一个长度为10的统计数组.
数组中存的是元素的出现次数,初始时出现次数都为0.2.通过遍历开始统计每个元素出现的次数:
count[array[i]]++;
当array[0]=4时,count[4]++ = 1;当array[1]=2时,count[2]++ = 1;
当array[2]=3时,count[3]++ = 1;当array[3]=9时,count[9]++ = 1;
当array[4]=4时,count[4]++ = 2;当array[5]=7时,count[7]++ = 1;
当array[6]=0时,count[0]++ = 1;当array[7]=1时,count[1]++ = 1;
当array[8]=1时,count[1]++ = 2;当array[9]=9时,count[9]++ = 2;
当array[10]=8时,count[8]++ = 1;当array[11]=2时,count[2]++ = 2;
当array[12]=5时,count[5]++ = 1;当array[13]=6时,count[6]++ = 1;
当array[14]=4时,count[4]++ = 3;当array[15]=3时,count[9]++ = 2;
经过统计:
0出现了1次,1出现了2次,2出现了2次,3出现了2次,4出现了3次.
5出现了1次,6出现了1次,7出现了1次,8出现了1次,9出现了2次.
3.根据计数的结果来回收数据,从count数组下标由小到大进行回收.
将count中的数据遍历出来依次往array中放,覆盖它原有的数据
代码实现如下:
public class CountSort{
static void printArray(int[] array){
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]+" ");
}
System.out.println();
}
public static void countSort(int[] array){
//初始时maxValue和minValue都放在数组第一个的位置.
int maxValue=array[0];
int minValue=array[0];
//通过遍历找出序列中最大的值和最小的值.
for(int i=0;i<array.length;i++){
if(array[i]>maxValue){
maxValue=array[i];
}
if(array[i]<minValue){
minValue=array[i];
}
}
//计算计数数组的长度.
int range=maxValue-minValue+1;
//创建计数数组
int[] count=new int[range];
//统计每个元素出现的次数.
for(int i=0;i<array.length;i++){
count[array[i]-minValue]++;
}
int index=0;
//根据统计结果回收count中的数据
for(int i=0;i<range;i++){
while(count[i]>0){
//数据出现几次就打印几次,并且将数据按照顺序覆盖到array中
//最后得到的就是一个有序列表.
array[index++]=i+minValue;
count[i]--;
}
}
}
public static void main(String[] args) {
int[] array={4,2,3,9,4,7,0,1,1,9,8,2,5,6,4,3};
//传入这个数组
countSort(array);
//打印排好序的数组
printArray(array);
}
}
计数排序的特性总结:
1.基数排序在数据范围集中时,效率很高,但是适用范围和场景有限.
2.时间复杂度:O(MAX(N,范围))
3.空间复杂度:O(范围)
4.稳定性:稳定
有什么错误或者有什么需要优化的地方,欢迎各位大佬来指正!!!