把n
个待排序的元素看成为一个有序表
和一个无序表
,开始时有序表
中只包含1
个元素,无序表
中包含有n-1
个元素,排序过程中每次从无序表中取出第一个
元素,把它的排序码依次与有序表元素的排序码进行比较,将它插入到有序表中的适当位置,使之成为新的有序表。
package pers.chh3213.sort; import java.util.Arrays; /** * DirectInsertSort.java * @Description 直接插入法 * @author chh3213 * @version * @date 2021年12月26日上午11:19:07 */ public class DirectInsertSort { public static void main(String[] args) { DirectInsertSort insertSort = new DirectInsertSort(); int[] arr = {9, -16, 310, 23, -30, -49, 25, 21, 30}; insertSort.directInsertSort(arr); System.out.println(Arrays.toString(arr)); } public void directInsertSort(int[] arr) { // 法一 for (int i = 1; i < arr.length; i++) { int temp = arr[i]; // 记录要插入的数据 int j=i; for ( ; j>0&&arr[j-1]>temp; j--) {// 从已经排序的序列最右边的开始比较,找到比其小的数 arr[j]=arr[j-1]; } if(j!=i)arr[j]=temp; } //法二 // for (int i = 1; i < arr.length; i++) { // for(int j=i;j>0;j--) { // if(arr[j]<arr[j-1])swap(arr, j, j-1); // } // } } public void swap(int[] arr, int i, int j) { int temp =arr[i]; arr[i]=arr[j]; arr[j]=temp; } }
n-1
次插入,每次插入最少比较一次(正序),移动0
次;最多比较i
次(包括同temp的比较),移动i+1
次(逆序)(i=2,3,…,n)。因此,直接插入排序的时间复杂度为
O
(
n
2
)
O(n^2)
O(n2) 。稳定
的。先将整个待排元素序列分割成若干个子序列(由相隔某个增量
的元素组成的)分别进行直接插入排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下(接近最好情况) ,效率是很高的,因此希尔排序在时间效率上有较大提高。
d1=8/2=4;
d2=4/2=2;
d3=2/2=1;
选择一个增量序列t1,t2,……,tk
,其中ti > tj
, tk = 1
;
按增量序列个数 k
,对序列进行 k
趟直接插入排序;
每趟排序,根据对应的增量 ti
,将待排序列分割成若干长度为m
的子序列,分别对各子表进行直接插入排序。仅增量因子为1
时,整个序列作为一个表来处理,表长度即为整个序列的长度。
package pers.chh3213.sort; import java.util.Arrays; public class ShellSort { public static void main(String[] args) { ShellSort shell = new ShellSort(); int[] arr = {9, -16, 310, 23, -30, -49, 25, 21, 30}; shell.shellSort(arr); System.out.println(Arrays.toString(arr)); } public void shellSort(int[] arr) { //第一次步长为数组长度/2,后面依次步长/2 for (int step = arr.length /2; step >0; step /= 2) { //直接插入排序 for (int i = step; i < arr.length; i++) { int temp = arr[i];//右侧待排序区第一个数 int j=i-step;//左侧已排序区域第一个数索引 for( ;j>=0&&arr[j]>temp;j-=step) { arr[j+step]=arr[j];//满足条件则把已排序数字往后挪一个位置 // swap(arr, j, j+step); } //插入待排序数字到指定位置 arr[j+step]=temp; } } } public void swap(int[] arr, int i, int j) { int temp =arr[i]; arr[i]=arr[j]; arr[j]=temp; } }
n
数量级的,内循环远远低于n
数量级,因为当分组较多时,组内元素少此循环次数少;当分组较少时,组内元素增多,但已接近有序,循环次数并不增加。因此,希尔排序的时间复杂性在
O
(
n
l
o
g
2
n
)
O(nlog_2n)
O(nlog2n)和
O
(
n
2
)
O(n^2)
O(n2)之间,大致为
O
(
n
1.3
)
O(n^{1.3})
O(n1.3) 。不稳定
的。冒泡排序通过重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。
原理描述
通过对待排序序列从前向后,依次比较相邻元素的排序码,若发现逆序则交换,使排序码较大的元素逐渐从前部移向后部。
实现步骤(默认升序的情况)
package pers.chh3213.sort; import java.util.Iterator; import java.util.Scanner; public class BubbleSort { public static void main(String[] args) { int[] arr = {5,4,1,966,2,3,56,89,12,0,56562}; System.out.println("before sort:"); for (int i : arr) { System.out.print(i+"\t"); } for (int i = 0; i < arr.length-1; i++) { for (int j = 0; j < arr.length-1-i; j++) { if(arr[j]>arr[j+1]) { int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } System.out.println(); System.out.println("after sort:"); for (int i : arr) { System.out.print(i+"\t"); } } }
因为排序的过程中,各元素不断接近自己的位置,如果一趟比较下来没有进行过交换,就说明序列有序, 因此可以在排序过程中设置一个标志swap判断元素是否进行过交换,从而减少不必要的比较。改进代码如下:
public void bubbleSort(int[] data) { for (int i = 0; i < data.length-1; i++) { boolean swap = false; for (int j = 0; j < data.length-i-1; j++) { if(data[j]>data[j+1]) { int temp = data[j]; data[j]= data[j+1]; data[j+1] = temp; swap = true; } } if(!swap)break; //不交换时停止排序 } }
(n-1)
次,移动元素次数为0
;若待排序的元素为逆序,则需进行n-1
趟排序,比较次数为
(
n
2
−
n
)
/
2
(n^2-n)/2
(n2−n)/2,移动次数为
3
(
n
2
−
n
)
/
2
3(n^2-n )/2
3(n2−n)/2,因此冒泡排序算法的时间复杂度为
O
(
n
2
)
O(n^2)
O(n2) 。由于其中的元素移动较多,所以属于内排序中速度较慢的一种。因为冒泡排序算法只进行元素间的顺序移动,所以是一个稳定的算法。1. 从数列中挑出一个元素,称为基准(pivot),一般取第一个元素; 2. 通过一次划分,将待排元素分为左右两个子序列,所有元素比基准值小的摆放在左序列,所有元素比基准值大的摆在右序列(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为**分区**(partition)操作; 3. 然后分别对两个子序列继续进行划分,直至每一个序列只有一个元素为止; 4. 最后得到的序列便是有序的序列。
(注:图片来源:参考资料1)
一次划分的具体过程
概括地说,一次划分就是从表的两端交替地向中间进行扫描,将小的放到左边,大的放到右边,作为标准的元素放到中间。
之后采用递归的方式分别对前半部分和后半部分排序,当前半部分和后半部分均有序时该数组就自然有序了。
一次划分的具体过程示例
8. 直到low==high时, R[low]=R[0] (即将作为标准的元素放到其最终位置)。
- 示例
package pers.chh3213.sort; public class QuickSort { public static void main(String[] args) { System.out.println("quick sort test"); int[] arr = {9, -16, 30, 23, -30, -49, 25, 21, 30}; System.out.println("before sort:"); for (int i : arr) { System.out.print(i+"\t"); } QuickSort quick = new QuickSort(); quick.quickSort(arr, 0, arr.length-1); System.out.println(); System.out.println("after sort:"); for (int i : arr) { System.out.print(i+"\t"); } } public void quickSort(int[] arr,int start, int end) { if(start<end) { int index = partition(arr, start, end); //将表一分为2 quickSort(arr, start, index-1); // 对左子序列进行快速排序 quickSort(arr, index+1, end); //对右子序列进行快速排序 } } // 一次划分 public int partition(int[] arr, int low,int high) { int base = arr[low]; //暂存基准元素到base while (low<high) {//从表的两端交替的向中间扫描 while(low<high && arr[high]>=base)high--;//右端扫描 if(low<high) { arr[low]=arr[high];//把比基准小的元素放到基准前面 low++; } while(low<high && arr[low]< base)low++;//左端扫描 if(low<high) { arr[high]=arr[low];//把比基准大的元素放到基准后面 high--; } } arr[low] = base;//把基准元素放到最终位置 return low;//返回基准元素所在的位置 } }
快速排序的递归过程可用一棵二叉树形象地给出。下图为待排序列4,38,65,97,76,13,27,49
所对应的快速排序递归调用过程的二叉树(简称为快速排序递归树)。
从快速排序算法的递归树可知,快速排序的趟数取决于递归树的高度。
如果每次划分对一个对象定位后,该对象的左子序列与右子
序列的长度相同,则下一步将是对两个长度减半的子序列进行排序,这是最理想的情况。
假设n是2的幂,
n
=
2
k
,
(
k
=
l
o
g
2
n
)
n=2^k,(k=log_2n)
n=2k,(k=log2n),假设基准位置位于序列中间,这样划分的子区间大小基本相等。
n
+
2
(
n
/
2
)
+
4
(
n
/
4
)
+
.
.
.
+
n
(
n
/
n
)
=
n
+
n
+
.
.
.
+
n
=
n
∗
k
=
n
∗
l
o
g
2
n
n+2(n/2)+4(n/4)+ ...+n(n/n)=n+n+ ...+n=n*k=n*log_2n
n+2(n/2)+4(n/4)+...+n(n/n)=n+n+...+n=n∗k=n∗log2n
因此,快速排序的最好时间复杂度为 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n) 。而且在理论上已经证明,快速排序的平均时间复杂度也为 O ( n l o g 2 n ) O ( nlog_2n) O(nlog2n) 。实验结果表明:就平均计算时间而言,快速排序是所有内排序方法中最好的一个。
在最坏的情况,即待排序对象序列已经按其排序码从小到大排好序的情况下,其递归树成为单支树,每次划分只得到一个比上一次少一个对象的子序列(蜕化为冒泡排序)。必须经过n-1
趟才能把所有对象定位,而且第i
趟需要经过n-i
次排序码比较才能找到第i
个对象的安放位置,总的排序码比较次数将达到
∑
i
=
1
n
−
1
(
n
−
i
)
=
1
2
n
(
n
−
1
)
≈
n
2
2
\sum_{i=1}^{n-1}{(n-i)}=\frac{1}{2}n(n-1) \approx \frac{n^2}{2}
∑i=1n−1(n−i)=21n(n−1)≈2n2
因此,快速排序的最坏时间复杂度为
O
(
n
2
)
O(n^2)
O(n2)。
栈
存放每层递归调用时的指针和参数。最大递归调用层次数与递归树的高度一致。理想情况为
l
o
g
2
(
n
+
1
)
log_2(n+1)
log2(n+1);最坏情况即待排序对象序列已经按其排序码从小到大排好序的情况下,其递归树成为单支树,深度为n
。因此,快速排序最好的空间复杂度为
O
(
l
o
g
2
n
)
O (log_2n)
O(log2n) ,最坏的空间复杂度为
O
(
n
)
O(n)
O(n)(即快速排序所需用的辅助空间)。R[i]
到R[n]
中选择具有最小关键码的元素package pers.chh3213.sort; import java.util.Arrays; public class SelectSort { public static void main(String[] args) { SelectSort select = new SelectSort(); int[] arr = {9, -16, 310, 23, -30, -49, 25, 21, 30}; select.selectSort(arr); System.out.println(Arrays.toString(arr)); } public void selectSort(int[] arr) { for (int i = 0; i < arr.length; i++) {//进行n-1趟排序 int min = i; for (int j = i+1; j < arr.length; j++) { if(arr[min]>arr[j])min=j; // 记录目前能找到的最小值元素的下标 } // 找到最小值后,再将找到的最小值和i位置所在的值进行交换 if(i!=min)swap(arr, i, min); } } public void swap(int[] arr, int i, int j) { int temp =arr[i]; arr[i]=arr[j]; arr[j]=temp; } }
无论初始状态如何,在第i
趟排序中选择最小关键码的元素,需做n-i
次比较,因此总的比较次数为:
∑
i
=
1
n
−
1
n
−
i
=
n
(
n
−
1
)
/
2
=
O
(
n
2
)
\sum_{i=1}^{n-1}{n-i}=n(n-1)/2=O(n^2)
∑i=1n−1n−i=n(n−1)/2=O(n2)(即时间复杂度)
最好情况:序列为正序时,移动次数为 0 0 0, 最坏情况:序列为反序时,每趟排序均要执行交换操作,总的移动次数取最大值 3 ( n − 1 ) 3(n-1) 3(n−1)。
由于在直接选择排序中存在着不相邻元素之间的互换,因此,直接选择排序是一种不稳定的排序方法。例如,给定排序码为3, 7, 3’, 2, 1,排序后的结果为1, 2, 3’, 3, 7
n个元素的序列{k1, k2 , .... , kn }
,当且仅当满足
{
k
i
≤
k
2
i
k
i
≤
k
2
i
+
1
(1)
\begin{cases} k_i\le k_{2i} \\ k_i \le k_{2i+1} \tag{1} \end{cases}
{ki≤k2iki≤k2i+1(1)
或者
{
k
i
≥
k
2
i
k
i
≥
k
2
i
+
1
(1)
\begin{cases} k_i\ge k_{2i} \\ k_i \ge k_{2i+1} \tag{1} \end{cases}
{ki≥k2iki≥k2i+1(1)
称之为堆。
若将此排序码按顺序组成一棵完全二叉树,则(1)称为小顶堆(二叉树的所有结点值小于或等于左右孩子的值) , (2)称为**大顶堆(**二叉树的所有结点值大于或等于左右孩子的值).
小顶堆和大顶堆示例
建初始堆
将排序码k1, k2, k, ..,kn
表示成一棵完全二叉树,然后从第n/2
个排序码(即树的最后一个非终端结点)开始筛选,使由该结点作根结点组成的子二叉树符合堆的定义
,然后从第n/2-1
个排序码重复刚才操作,直到第一个排序码止。这时候,该二叉树符合堆的定义,初始堆已经建立。
堆排序
将堆中第一个结点(二叉树根结点)和最后一个结点的数据进行交换(k1,与kn,),再将
k
1
k_1
k1~
k
n
−
1
k_{n-1}
kn−1,重新建堆,然后k1,和k_{n-2}交换,如此重复下去,每次重新建堆的元素个数不断减1,直到重新建堆的元素个数仅剩一个为止。这时堆排序已经完成,则排序码
k
1
,
k
2
,
k
3
,
.
.
,
k
n
k1, k2, k3, .., kn
k1,k2,k3,..,kn已排成一个有序序列。
堆排序的两大步骤
堆排序的关键问题
示例
(图片来源:参考资料3)
特点
package pers.chh3213.sort; import java.util.Arrays; /** * * MergeSort.java * @Description 归并排序 * @author chh3213 * @version * @date 2021年12月26日下午4:54:53 */ public class MergeSort { public static void main(String[] args) { MergeSort Sort = new MergeSort(); int[] arr = {9, -16, 310, 23, -30, -49, 25, 21, 30}; Sort.mergeSort(arr,0,arr.length-1); System.out.println(Arrays.toString(arr)); } public void mergeSort(int[] arr,int left, int right) { int mid = (left+right)/2; if(left<right) { //递归 mergeSort(arr, left, mid);//左边归并排序,使得左子序列有序 mergeSort(arr, mid+1, right);//右边归并排序,使得右子序列有序 //合并 merge(arr, left, right, mid);//将两个有序子数组合并操作 } } public void merge(int[] arr, int left,int right, int mid) { /* * 将两个有序数组合并 */ int[] temp = new int[right-left+1]; //建好一个临时数组 int i=left; //左子序列索引(理解成指针) int j = mid+1;//右子序列索引(理解成指针) int k =0;//临时数组的索引(理解成指针) while(i<=mid && j<=right) { if(arr[i]<=arr[j]) { temp[k++]=arr[i++]; } else { temp[k++]=arr[j++]; } } while(i<=mid)temp[k++]=arr[i++];//将左子序列剩余元素填充进temp中 while(j<=right)temp[k++]=arr[j++];//将右子序列剩余元素填充进temp中 //将temp中的元素全部拷贝回原数组中 for (int k2 = 0; k2 < temp.length; k2++) { arr[k2+left]=temp[k2]; } } }
n
个元素的表,将这n
个元素看作叶结点,若将两两归并生成的子表看作它们的父结点,则归并过程对应由叶向根生成一棵二叉树的过程。所以归并趟数等于二叉数的高度减1,即
l
o
g
2
n
log_2n
log2n。每一趟归并需移动n
个元素,即每一趟归并的时间复杂度为
O
(
n
)
O(n)
O(n)。因此, 二路归并排序的时间复杂度为
O
(
n
l
o
g
2
n
)
O(nlog_2n)
O(nlog2n)。