Java数据结构之基于比较的排序算法基本原理及具体实现

Java数据结构之基于比较的排序算法基本原理及具体实现

目录1. 七大基于比较的排序-总览1.1常见基于比较的排序分类1.2时间复杂度，空间复杂度以及稳定性。2.直接插入排序2.1 直接插入排序的基本思想2.2 直接插入排序动画演示2.3 代码示例2.4 时间复杂度，空间复杂度以及稳定性3. 希尔排序3.1 算法思想3.2 图片演示3.3 代码示例3.4 时间复杂度，空间复杂度以及稳定性4.选择排序4.1 算法思想4.2 动画演示4.3 代码示例4.4 时间复杂度，空间复杂度以及稳定性5.堆排序5.1 算法思想5.2 动画演示5.3 代码示例5.4 时间复杂度，空间复杂度以及稳定性6.冒泡排序6.1 算法思想6.2 动画演示6.3 代码示例6.4 时间复杂度，空间复杂度以及稳定性7.快速排序（十分重要）7.1 算法思想7.2 动画演示7.3 代码示例7.4 时间复杂度，空间复杂度以及稳定性8.归并排序8.1 算法思想8.2 动画演示8.3 代码示例8.4 时间复杂度，空间复杂度以及稳定性

基于比较的排序算法基本原理及java实现

1. 七大基于比较的排序-总览

1.1常见基于比较的排序分类

1.2时间复杂度，空间复杂度以及稳定性。

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。

不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。

2.直接插入排序

2.1 直接插入排序的基本思想

直接插入排序的基本思想，就是每次选取一个待排序元素，按照一定规定插入到前面已经排好序的一组元素的适当位置。当每个元素都插入完毕，整个序列已经有序。

当插入第i(i >= 1)时，前面的V[0]，V[1]，……，V[i-1]已经排好序。这时，用V[I]的排序码与V[i-1]，V[i-2]，…的排序码顺序进行比较，找到插入位置即将V[i]插入，原来位置上的元素向后顺移。

2.2 直接插入排序动画演示

2.3 代码示例

public static void insertSort(int[] arr){

for(int i=1;i

int j=i-1;//i之前的序列 已经有序

int temp=arr[i];

for(;j>=0;j--){//此循环用于寻找插入位置

if(arr[j]>temp){//此时逐个向后移动元素

arr[j+1]=arr[j];

}else break;//找到插入位置 直接break

}

arr[j+1]=temp;//直接插入

}

}

2.4 时间复杂度，空间复杂度以及稳定性

时间复杂度最坏情况：数组整体逆序O(n^2);

时间复杂度最好情况：数组已经有序O(n^2);

空间复杂度:O(1);

稳定性：稳定;

3. 希尔排序

3.1 算法思想

希尔排序是特殊的插入排序，直接插入排序每次插入前的遍历步长为1，而希尔排序是将待排序列分为若干个子序列，对这些子序列分别进行直接插入排序，当每个子序列长度为1时，再进行一次直接插入排序时，结果一定是有序的。常见的划分子序列的方法有：初始步长（两个子序列相应元素相差的距离）为要排的数的一半，之后每执行一次步长折半。

3.2 图片演示

3.3 代码示例

public static void hell(int[] arr,int gap){//当gap=1时 其实就是直接插入排序

for(int i=gap;i

int j=i-gap;

int temp=arr[i];

for(;j>=0;j-=gap){

http:// if(arr[j]>temp){

arr[j+gap]=arr[j];

}else break;

}

arr[j+gap]=temp;

}

}

public static void hellSort(int[] arr){

int gap=arr.length;

while(gap>1){

gap=gap/2+1;

hell(arr,gap);

}

}

3.4 时间复杂度，空间复杂度以及稳定性

时间复杂度最好：O(n);

时间复杂度最坏：O(n^1.5);

时间复杂度平均：O(n^1.3);

空间复杂度：O(1);

稳定性：不稳定;

4.选择排序

4.1 算法思想

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

4.2 动画演示

4.3 代码示例

public static void selectSort(int[] arr){

for(int i=0;i

for(int j=i+1;j

if(arr[j]

int temp=arr[j];

http:// arr[j]=arr[i];

arr[i]=temp;

}

}

}

}

4.4 时间复杂度，空间复杂度以及稳定性

时间复杂度最好：O(n);

时间复杂度最坏：O(n^2;

时间复杂度平均：O(n^2);

空间复杂度：O(1);

稳定性：不稳定;

5.堆排序

5.1 算法思想

堆

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：

将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；

将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；

由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

5.2 动画演示

5.3 代码示例

public static void heapSort(int[] arr){//排序方法

creatHeap(arr);

int end=arr.length-1;

//因为是大根堆，所以根节点值为最大值，根节点与最后一个节点值交换 输出并删除此时最后一个节点，然后向下调整根节点

while(end>0){

int temp=arr[0];

arr[0]=arr[end];

arr[end]=temp;

shiftDown(arr,0,end);

end--;

}

}

public static void creatHeap(int[] arr){//建堆

for(int parent=(arr.length-1-1)/2;parent>=0;parent--){

shiftDown(arr,parent,arr.length);

}

}

public static void shiftDown(int[]arr,int root,int len){//向下调整操作

int parent=root;

int child=parent*2+1;

while(child

if(child+1

child++;

}

if(arr[child]>arr[parent]){//由于是大根堆，如果儿子节点值大于父亲节点就交换

int temp=arr[parent];

arr[parent]=arr[child];

arr[child]=temp;

parent=child;//继续向下调整，防止调整后不满足大根堆的条件

child=parent*2+1;

}else break;

}

}

5.4 时间复杂度，空间复杂度以及稳定性

时间复杂度最好：O(nlogn);

时间复杂度最坏：O(nlogn);

时间复杂度平均：O(nlogn);

空间复杂度：O(1);

稳定性：不稳定;

6.冒泡排序

6.1 算法思想

比较两个相邻的元素，将值大的元素交换到右边

思路：依次比较相邻的两个数，将比较小的数放在前面，比较大的数放在后面。

1.第一次比较：首先比较第一和第二个数，将小数放在前面，将大数放在后面。

2.比较第2和第3个数，将小数 放在前面，大数放在后面。

3.如此继续，知道比较到最后的两个数，将小数放在前面，大数放在后面，重复步骤，直至全部排序完成

4.在上面一趟比较完成后，最后一个数一定是数组中最大的一个数，所以在比较第二趟的时候，最后一个数是不参加比较的。

5.在第二趟比较完成后，倒数第二个数也一定是数组中倒数第二大数，所以在第三趟的比较中，最后两个数是不参与比较的。

6.依次类推，每一趟比较次数减少依次

6.2 动画演示

6.3 代码示例

public static void bubbleSort(int[] arr){

for(int i=0;i

boolean flag=false;//一个标记进行优化

for(int j=0;j

if(arr[j]>arr[j+1]){

int temp=arr[j];

arr[j]=arr[j+1];

arr[j+1]=temp;

flag=true;

}

}

if(flag==false) break;//如果一趟循环走完没有交换，说明已经有序，直接break

}

}

6.4 时间复杂度，空间复杂度以及稳定性

时间复杂度最好：O(n);

时间复杂度最坏：O(n^2);

时间复杂度平均：O(n^2);

空间复杂度：O(1);

稳定性：稳定

7.快速排序（十分重要）

7.1 算法思想

我们从数组中选择一个元素，我们把这个元素称之为中轴元素吧，然后把数组中所有小于中轴元素的元素放在其左边，所有大于或等于中轴元素的元素放在其右边，显然，此时中轴元素所处的位置的是有序的。也就是说，我们无需再移动中轴元素的位置。

从中轴元素那里开始把大的数组切割成两个小的数组(两个数组都不包含中轴元素)，接着我们通过递归的方式，让中轴元素左边的数组和右边的数组也重复同样的操作，直到数组的大小为1，此时每个元素都处于有序的位置。

7.2 动画演示

7.3 代码示例

//该代码参考acwing创始人yxc的快排模板

public static void quickSort(int[] arr,int l,int r){

if(l>=r) return;//每次判断传进来左右下标

int i=l-1,j=r+1;//因为在循环中，要先i++，j--所以i，j定义为两边界偏移1

int x=arr[(l+r)/2];//取x为数组中间位置数

while(i

do i++;while(arr[i]

do j--;while(arr[j]>x);

//此时i指向的数字大于中轴数字， j指向数字小于中轴数字 交换

if(i

int temp=arr[i];

arr[i]=arr[j];

arr[j]=temp;

}

}

quickSort(arr,l,j);//退出循环是i==j 递归排序

quickSort(arr,j+1,r);

}

7.4 时间复杂度，空间复杂度以及稳定性

时间复杂度最好：O(nlog2n);

时间复杂度最坏：O(n^2);

时间复杂度平均：O(nlog2n);

空间复杂度：O(nlog2n);

稳定性：不稳定;

8.归并排序

8.1 算法思想

将一个大的无序数组有序，我们可以把大的数组分成两个，然后对这两个数组分别进行排序，之后在把这两个数组合并成一个有序的数组。由于两个小的数组都是有序的，所以在合并的时候是很快的。

通过递归的方式将大的数组一直分割，直到数组的大小为 1，此时只有一个元素，那么该数组就是有序的了，之后再把两个数组大小为1的合并成一个大小为2的，再把两个大小为2的合并成4的 …… 直到全部小的数组合并起来。

8.2 动画演示

8.3 代码示例

public static void mergerSort(int[]arr){

mergerSortInternal(arr,0,arr.length-1);

}

public static void mergerSortInternal(int[]arr,int l,int r) {//

if (l >= r) return;

int mid = (l + r) / 2;//把数组分为两个

mergerSortInternal(arr, l, mid);//对左边数组递AbvikbbCs归排序

mergerSortInternal(arr, mid + 1, r);//对右边数组递归排序

merge(arr,l,mid,r);//排序完成，进行合并

}

public static void merge(int[]arr,int low,int mid,int high){

int s1=low;//mid左侧数组的头和尾

int e1=mid;

int s2=mid+1;//mid右侧数组的头和尾

int e2=high;

int[]temp=new int[high-low+1];//定义一个数字，用来合并他们

int k=0;//指示数组下标

while(s1<=e1&&s2<=e2){//选出两侧数组最小元素 插入temp数组

if(arr[s1]<=arr[s2]) temp[k++]=arr[s1++];

else temp[k++]=arr[s2++];

}

while(s1<=e1) temp[k++]=arr[s1++];//如果一侧数组插入完毕，另一侧还有剩余，则全部插入

while(s2<=e2) temp[k++]=arr[s2++];

for(int i=0;i

arr[i+low]=temp[i];

}

}

}

8.4 时间复杂度，空间复杂度以及稳定性

时间复杂度最好：O(nlog2n);

时间复杂度最坏：O(nlog2n);

时间复杂度平均：O(nlog2n);

空间复杂度：O(n);

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。