• Home
  • Java Data Structures and Algorithms Lesson 9 - Sorting

Java Data Structures and Algorithms Lesson 9 - Sorting

Knowing & Doing 2022-08-06 18:15:05 阅读数:595

javadatastructuresalgorithmslesson

一：Some sort of idea

​
排序：所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作.
稳定性：假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的.例如：
在这里插入图片描述
内部排序：数据元素全部放在内存中的排序.
外部排序：数据元素太多不能同时放在内存中,根据排序过程的要求不能在内外存之间移动数据的排序.
​

二:排序分类

排序分类

三：The introduction of common sorting algorithms

3.1直接插入排序

3.1.1基本思想

 直接插入排序是一种简单的插入排序法,其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 .实际中我们玩扑克牌时,就用了插入排序的思想.

3.1.2图解+步骤

​在这里插入图片描述
Direct insertion sort is similar to the code card when we play poker,如上面左图所示.
At that time came again a red peach9,After I compare in turn.红桃A比9大,The red peachA就往后移动一位;Then compare the red peachK,比9大,红桃K也向后移动一位…依次类推,The red peach until10,红桃10也比9大,红桃10向后移动一位,把红桃9Inserted into the front of the.这就是插入排序.
步骤如下:

  • 步骤1: 从第一个元素开始,该元素可以认为已经被排序;
  • 步骤2: 取出下一个元素,在已经排序的元素序列中从后向前扫描;
  • 步骤3: 如果该元素（已排序）大于新元素,将该元素移到下一位置;
  • 步骤4: 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
  • 步骤5: 将新元素插入到该位置后;
  • 步骤6: 重复步骤2~5.

​ 插入排序,Like a code card;从后往前,依次比较;
The head back,Those who stay;找准位置,插入其中.

3.1.3代码实现

package Sort;
import java.util.Arrays;
public class TestSort {

/** * 直接插入排序 * @param array */
public static void insertSort(int[] array) {

for(int i = 1;i < array.length;i++) {

int tmp = array[i];
int j = i-1;
for (; j >= 0 ; j--) {

if(array[j] > tmp) {

array[j+1] = array[j];
}else {

//array[j+1] = tmp;
break;
}
}
array[j+1] = tmp;
}
}
public static void main(String[] args) {

int[] array = {
2,1,53,4,5,10,9,36,23,6,19};
System.out.println("排序前："+ Arrays.toString(array));
insertSort(array);
System.out.println("排序后："+ Arrays.toString(array));
}
}

运行结果

3.1.4 直接插入排序总结

  1. 时间复杂度:O(N^2),最坏情况下,Array is completely reverse the situation,Its time complexity is an arithmetic progression.
  2. 空间复杂度:O(1),Do not create additional space.
  3. 稳定性:稳定
  4. 适用场景:当数据量小,并且已经趋于有序的时候,使用直接插入排序.

3.2希尔排序

3.2.1基本思想

希尔排序是希尔（Donald Shell） 于1959年提出的一种排序算法.希尔排序也是一种插入排序,It is a direct insertion sort after the improved version of a more efficient,也称为缩小增量排序,同时该算法是冲破O(N^2）的第一批算法之一.

3.2.2图解+步骤

在这里插入图片描述
我们可以发现,In the process of hill sort,With the continuous decrease of number of clusters,The overall data more and tend to order.当gap=1时,Is equivalent to the overall carried out a direct insertion sort,At this point we need to grasp two:

  1. At this time the whole array has been tending to order,So use direct insertion sort,The efficiency can reach almostO(N),是非常高效的;
  2. 最后一轮排序时gap=1,Can achieve the result of the whole array orderly at this time;So no matter how to group in front of us,例如分为521组,631组,甚至741组,都可以,But the final group must begap=1.

The discussion about how to group:
在这里插入图片描述
在这里插入图片描述
In hill sorting exactly how the group is the most efficient,众说纷纭,Also presents different views in different books.But as we previously mentioned,No matter which kind of points method,最后一个增量值必须等于1.
步骤如下:

  • 步骤1：选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;
  • 步骤2：按增量序列个数k,对序列进行k 趟排序;
  • 步骤3：每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序.仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度.

希尔排序,分而治之;分成多组,Each order;
增量序列,In the end is a;提高效率,希尔排序.

3.2.3代码实现

package Sort;
import java.util.Arrays;
public class TestSort {

/** * 希尔排序 */
public static void shellSort(int[] array){

int gap = array.length;
while (gap > 1){

shell(array,gap);
gap /= 2;
}
shell(array,1);
}
private static void shell(int[] array, int gap) {

for(int i = gap;i < array.length;i++) {

int tmp = array[i];
int j = i-gap;
for (; j >= 0 ; j -= gap) {

if(array[j] > tmp) {

array[j+gap] = array[j];
}else {

break;
}
}
array[j+gap] = tmp;
}
}
public static void main(String[] args) {

int[] array = {
2,1,53,4,5,10,9,36,23,6,19};
System.out.println("排序前："+ Arrays.toString(array));
shellSort(array);
System.out.println("排序后："+ Arrays.toString(array));
}
}

运行结果

3.2.4总结

  1. 时间复杂度:与增量有关,Is by taking incremental(gap)的一个函数.According to the YanWeiMin versions,为O(N1.3)~O(N1.5).
  2. 空间复杂度:O(1),Do not create additional space.
  3. 稳定性:不稳定
  4. 适用场景:当数据量较大时,Hill sorting can be used,降低时间复杂度,对直接插入排序进行优化.

3.3选择排序

3.3.1基本思想

每一次从待排序的数据元素中选出最小（或最大）的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完 .

3.3.2图解+步骤

在这里插入图片描述
步骤如下:

  1. 步骤1：初始状态：无序区为R[1…n],有序区为空;
  2. 步骤2：第i趟排序(i=1,2,3…n-1)开始时,当前有序区和无序区分别为R[1…i-1]和R(i…n）.该趟排序从当前无序区中-选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1…i]和R[i+1…n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区;
  3. 步骤3：n-1趟结束,数组有序化了.

3.3.3代码实现

package Sort;
import java.util.Arrays;
public class TestSort {

/** * 选择排序 * @param */
public static void selectSort(int[] array) {

for (int i = 0; i < array.length; i++) {

int minIndex = i;
for (int j = i+1; j < array.length; j++) {

if(array[j] < array[minIndex]) {

minIndex = j;
}
}
swap(array,minIndex,i);
}
}
private static void swap(int[] array,int i,int j) {

int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
public static void main(String[] args) {

int[] array = {
2,1,53,4,5,10,9,36,23,6,19};
System.out.println("排序前："+ Arrays.toString(array));
selectSort(array);
System.out.println("排序后："+ Arrays.toString(array));
}
}

运行结果

3.3.4选择排序总结

  1. 时间复杂度:O(N*N).
  2. 空间复杂度:O(1),Do not create additional space.
  3. 稳定性:不稳定
  4. 适用场景:Usually not how with.

3.4堆排序

3.4.1基本思想

堆排序（Heapsort） 是指利用堆这种数据结构所设计的一种排序算法.堆积是一个近似完全二叉树的结构,并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点.需要注意的是排升序要建大堆,排降序建小堆.

3.4.2图解+步骤

在这里插入图片描述

  1. 步骤1：将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆,此堆为初始的无序区;
  2. 步骤2：将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n];
  3. 步骤3：由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn).不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成.

3.4.3代码实现

package Sort;
import java.util.Arrays;
public class TestSort {

/** * 堆排序 * @param array */
public static void heapSort(int[] array){

createHeap(array); //建立大根堆
int end = array.length - 1;
while (end >= 0){

swap(array,0,end);
shiftDown(array,0,end);
end--;
}
}
private static void createHeap(int[] array) {

for(int p = (array.length-1-1)/2; p >= 0;p--){

shiftDown(array,p,array.length);
}
}
private static void shiftDown(int[] array, int root, int len) {

int parent = root;
int child = (2*parent) + 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 = 2*parent + 1;
} else {

break;
}
}
}
public static void main(String[] args) {

int[] array = {
2,1,53,4,5,10,9,36,23,6,19};
System.out.println("排序前："+ Arrays.toString(array));
heapSort(array);
System.out.println("排序后："+ Arrays.toString(array));
}
}

运行结果

3.4.4堆排序总结

  1. 时间复杂度:O(N*logN).
  2. 空间复杂度:O(1),Do not create additional space.
  3. 稳定性:不稳定

3.5冒泡排序

3.5.1基本思想

冒泡排序 是一种简单的排序算法.它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误,就把它们交换过来.走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端.

3.5.2图解+步骤

冒泡排序图解

对于冒泡排序,After each round of sorts,The last element of the wheels will be ordered.也就是说,Bubble sort is a constant element will be the biggest"冒泡"At the end of the order.
具体步骤如下:

  1. 步骤1: 比较相邻的元素.如果第一个比第二个大,就交换它们两个;
  2. 步骤2: 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
  3. 步骤3: 针对所有的元素重复以上的步骤,除了最后一个;
  4. 步骤4: 重复步骤1~3,直到排序完成.

3.5.3代码实现

package Sort;
import java.util.Arrays;
public class TestSort {

/** * 冒泡排序 * @param array */
public static void bubbleSort(int[] array){

for (int i = 0; i < array.length-1; i++) {

boolean flag = false;
for (int j = 0; j < array.length-1-i; j++) {

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

flag = true;
int tmp = array[j];
array[j] = array[j+1];
array[j+1] = tmp;
}
if(!flag){

break;
}
}
}
}
public static void main(String[] args) {

int[] array = {
2,1,53,4,5,10,9,36,23,6,19};
System.out.println("排序前："+ Arrays.toString(array));
bubbleSort(array);
System.out.println("排序后："+ Arrays.toString(array));
}
}

运行结果

3.5.4总结

  1. 时间复杂度:O(N^2).
  2. 空间复杂度:O(1),Do not create additional space.
  3. 稳定性:稳定
    4.使用场景:If the array is tend to be more orderly,使用冒泡[]Sorting is very good.在进行优化后,如果数组有序,So the time complexity of the bubble sort will reachO(N).

3.6快速排序

3.6.1基本思想

通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序.

3.6.2步骤

具体步骤如下:

  1. 步骤1：从数列中挑出一个元素,称为 “基准”（pivot ）;

  2. 步骤2：重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）.在这个分区退出之后,该基准就处于数列的中间位置.这个称为分区（partition）操作;

  3. 步骤3：递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序.

     我们要知道,Could be divided into both the left and right sides of the interval according to the basic value method there are many kinds of,Here I will introduce:Hoare法,挖坑法,And both before and after the pointer method.这三种方法,To dig a hole method is the most common again.

3.6.3Different methods to realize quick sort

3.6.3.1Hoare法

3.6.3.1.1具体操作
  • HoareMethod need two"指针",low指向前,high指向后;
  • Here we will be the first element of the array as the benchmark,让low和highTo the middle mobile;lowPointer does not stop is greater than the benchmark values,highPointer to meet value is smaller than benchmark stop,At this time the exchange;
  • 重复第二步,直到low 与high相遇,At this time will meet the value of the position and basic value exchange;
  • The basic value is smaller than benchmark elements to the left of the,On the right side of the basic value is larger than the basic value elements.
  • In turn recursive start points to the left of the arrays and the right of the basic value,直到整个数组有序,递归结束,排序完成.

特别注意:

  • If it is on the left side of elements as the basic value,那么右边的high先移动;If it is left and right boundary element as the basic value,那么左边的low先移动.

在这里插入图片描述
在这里插入图片描述

3.6.3.1.2代码实现
package Sort;
import java.util.Arrays;
public class TestSort {

/** * 快速排序 * @param array */
public static void quickSort(int[] array) {

quick(array,0,array.length-1);
}
private static void quick(int[] array, int left, int right) {

if(left >= right) return;
int pivot = partitionHoare(array,left,right);
quick(array,left,pivot-1);
quick(array,pivot+1,right);
}
private static int partitionHoare(int[] array, int low, int high) {

//To select the first element in the array as a benchmark for example
//首先,Need to save the first element of the array
int i = low;
int tmp = array[low];
while(low < high){

//1.如果low与highNo cross andhigh下标元素＞=基准值,high--继续找
while(low < high && array[high] >= tmp){

high--;
}
//出循环,说明此时highIs the number of you are looking for
//2.如果low与highNo cross andlow下标元素<=基准值,low++继续找
while(low < high && array[high] <= tmp){

low++;
}
//出循环,说明此时lowIs the number of you are looking for
swap(array,low,high);
}
//出循环,此时low与high相遇,Will meet again in the value of the basic value and exchange
swap(array,low,i);
return low;
}
public static void main(String[] args) {

int[] array = {
2,1,53,4,5,10,9,36,23,6,19};
System.out.println("排序前："+ Arrays.toString(array));
quickSort(array);
System.out.println("排序后："+ Arrays.toString(array));
}
}

在这里插入图片描述

3.6.3.2挖坑法

3.6.3.2.1具体操作
  1. 设定一个基准值（一般为序列的最左边元素,Also can be the rightmost element）此时最左边的是一个坑.
  2. 开辟两个指针,分别指向序列的头结点和尾结点（选取的基准值在左边,则先从右边出发.反之,选取的基准值在右边,则先从左边出发）.
  3. 从右指针出发Traversal sequence in turn,如果找到一个值比所选的基准值要小,则将此指针所指的值放在坑里,左指针向前移.
  4. 后从左指针出发（选取的基准值在左边,则后从左边出发.反之,选取的基准值在右边,则后从右边出发）,Traversal sequence in turn,如果找到一个值比所选的基准值要大,则将此指针所指的值放在坑里,右指针向前移.
  5. 依次循环步骤4,5,直到左指针和右指针重合时,We put basic value in both the position of the pointer overlap.
    在这里插入图片描述
    To dig a hole method,Need to pay attention to the so-called"坑"It is not a empty elements,But it is a to be covered"元素".
3.6.3.2.2代码实现
package Sort;
import java.util.Arrays;
public class TestSort {

/** * 快速排序 * @param array */
public static void quickSort(int[] array) {

quick(array,0,array.length-1);
}
private static void quick(int[] array, int left, int right) {

if(left >= right) return;
int pivot = partitionHole(array,left,right);
quick(array,left,pivot-1);
quick(array,pivot+1,right);
}
/* 这是Hole法 */
private static int partitionHole(int[] array, int low, int high) {

int tmp = array[low];
while(low < high){

while(low < high && array[high] >= tmp){

high--;
}
array[low] = array[high];
while(low < high && array[low] <= tmp){

low++;
}
array[high] = array[low];
}
array[low] = tmp;
return low;
}
// private static void insertSortRange(int[] array, int left, int right) {

// }
public static void main(String[] args) {

int[] array = {
2,1,53,4,5,10,9,36,23,6,19};
System.out.println("排序前："+ Arrays.toString(array));
quickSort(array);
System.out.println("排序后："+ Arrays.toString(array));
}
}

在这里插入图片描述

3.6.3.3前后指针法

3.6.3.3.1具体操作
  1. 1.定义两个指针,一个是i,一个是d;
  2. 每次for循环,i++;Every time meet basic value is less than the current element,d++;
  3. Each time at the same time, met the current element is less than the benchmark values,To exchange the subscripti和下标d的值.
  4. 当i>.high时,交换array[d-1]和array[low]的值,The end of the task.
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
3.6.3.3.2代码实现
package Sort;
import java.util.Arrays;
public class TestSort {

/** * 快速排序 * @param array */
public static void quickSort(int[] array) {

quick(array,0,array.length-1);
}
private static void quick(int[] array, int left, int right) {

if(left >= right) return;
int pivot = partitionPoint(array,left,right);
quick(array,left,pivot-1);
quick(array,pivot+1,right);
}
/* 前后指针法 */
private static int partitionPoint(int[] array, int left, int right) {

int d = left + 1;
int pivot = array[left];
for (int i = left + 1; i <= right; i++) {

if (array[i] < pivot) {

swap(array, i, d);
d++;
}
}
swap(array, d - 1, left);
return d - 1;
}
public static void main(String[] args) {

int[] array = {
2,1,53,4,5,10,9,36,23,6,19};
System.out.println("排序前："+ Arrays.toString(array));
quickSort(array);
System.out.println("排序后："+ Arrays.toString(array));
}
}

在这里插入图片描述

3.6.4总结

1.时间复杂度:O(N*logN).
但是,当数组有序时,At this time will be a single branch of the binary tree is constructed,Its time complexity toO(N2).Some people talk,Quick sort degradation has become a bubble sort at this time,Because of their time complexity is the same,But that's not serious,Quick sort and sort bubble sort is two completely different,The thought of quick sort bubble sort does not meet the.
2.空间复杂度: 最好情况下:O(logN);最坏情况下,O(N),Is a single branch tree.
3.稳定性:不稳定

When you want to use quick sort,Preferred method of digging holes,Hoare次之,The last is pointer method before and after.
其次,In the light of the quick sort space complexity is higher,Need to open up a lot of memory space on the stack,So we need to optimize the quick sort of,Can use.Optimization method basically has the following several kinds of:

3.6.5快排优化

3.6.5.1优化方法一:With the help of a direct insertion sort

3.6.5.1.1优化思路

每次递归的时候,The data are in slowly weave and orderly!!当数据量少且趋于有序的时候,我们可以使用直接插入排序进行优化.

3.6.5.1.2代码实现

package Sort;
import java.util.Arrays;
public class TestSort {

/** * 快速排序 * @param array */
public static void quickSort(int[] array) {

quick(array,0,array.length-1);
}
private static void quick(int[] array, int left, int right) {

if(left >= right) return;
//在某个区间的时候,使用直接插入排序{The comparison of optimal range}
if(right-left+1 <= 5){

//进行插入排序
insertSortRange(array,left,right);
return;
}
int pivot = partitionHole(array,left,right);
quick(array,left,pivot-1);
quick(array,pivot+1,right);
}
private static void insertSortRange(int[] array, int left, int right) {

for(int i = left+1;i <= right;i++) {

int tmp = array[i];
int j = i-1;
for (; j >= left ; j--) {

if(array[j] > tmp) {

array[j+1] = array[j];
}else {

//array[j+1] = tmp;
break;
}
}
array[j+1] = tmp;
}
}
/* 这是Hole法 */
private static int partitionHole(int[] array, int low, int high) {

int tmp = array[low];
while(low < high){

while(low < high && array[high] >= tmp){

high--;
}
array[low] = array[high];
while(low < high && array[low] <= tmp){

low++;
}
array[high] = array[low];
}
array[low] = tmp;
return low;
}
public static void main(String[] args) {

int[] array = {
2,1,53,4,5,10,9,36,23,6,19};
System.out.println("排序前："+ Arrays.toString(array));
quickSort(array);
System.out.println("排序后："+ Arrays.toString(array));
}
}

在这里插入图片描述
需要注意的是,This method has not been fundamentally achieve optimization.

3.6.5.2优化方法二:随机选取基准法

3.6.5.2.1优化思路

快速排序的运行时间与划分是否对称有关.最坏情况下,每次划分过程产生两个区域分别包含n-1个元素和1个元素,其时间复杂度会达到O(N^2).在最好的情况下,每次划分所取的基准都恰好是中值,即每次划分都产生两个大小为n/2的区域.此时,快排的时间复杂度为O(NlogN).So it is very important to the choice of benchmark for fast row.
在前面的文章中,Use array the leftmost element as the basic value.随机选取基准,Is in all elements of the rest of the elements in addition to the left,Randomly selected to an element as the basic value,This value with the leftmost element exchange.其余步骤,With the above mentioned the quick sort method is the same.
Although using basic random benchmarks can solve to row array orderly situation,But because of this randomness,Array will have impact on other cases(If the array elements are random,Using a fixed benchmark often better than random benchmark).随机数算法随机选择一个元素作为划分基准,算法的平均性能较好,从而避免了最坏情况的多次发生.However, random algorithm, after all, is a test of character learning,Selection is also difficult to guarantee the basic value to a more appropriate.
Such as shown below to sort an array,If we are in addition to the first element6All elements of the rest of the outside in,Select an element in the method of randomly selected benchmark,If you choose to just1,那么恭喜你,Successfully improved the sort of time,Reduce the efficiency of sorting.所以可见,Randomly selected is not a satisfactory way.
在这里插入图片描述

3.6.5.2.2代码实现

package Sort;
import java.sql.SQLOutput;
import java.util.Arrays;
import java.util.Random;
public class TestSort {

/** * 快速排序 * @param array */
public static void quickSort(int[] array) {

quick(array,0,array.length-1);
}
private static void quick(int[] array, int left, int right) {

if(left >= right) return;
// 1.在某个区间的时候,使用直接插入排序{The comparison of optimal range}
if(right-left+1 <= 5){

//进行插入排序
insertSortRange(array,left,right);
return;
}
// 2.随机选取基准法
int index = RandomIndex(array,left,right);
swap(array,left,index);
//int pivot = partitionHoare(array,left,right);
int pivot = partitionHole(array,left,right);
//int pivot = partitionPoint(array,left,right);
quick(array,left,pivot-1);
quick(array,pivot+1,right);
}
private static int RandomIndex(int[] array, int left, int right) {

Random random = new Random();
int index = random.nextInt(right);
return index;
}
private static void insertSortRange(int[] array, int left, int right) {

for(int i = left+1;i <= right;i++) {

int tmp = array[i];
int j = i-1;
for (; j >= left ; j--) {

if(array[j] > tmp) {

array[j+1] = array[j];
}else {

//array[j+1] = tmp;
break;
}
}
array[j+1] = tmp;
}
}
/* 这是Hole法 */
private static int partitionHole(int[] array, int low, int high) {

int tmp = array[low];
while(low < high){

while(low < high && array[high] >= tmp){

high--;
}
array[low] = array[high];
while(low < high && array[low] <= tmp){

low++;
}
array[high] = array[low];
}
array[low] = tmp;
return low;
}
public static void main(String[] args) {

int[] array = {
2,1,53,4,5,10,9,36,23,6,19};
System.out.println("排序前："+ Arrays.toString(array));
quickSort(array);
System.out.println("排序后："+ Arrays.toString(array));
}
}

在这里插入图片描述
The above code USES a randomly selected benchmark method.因为数据量很少,Also it will be difficult to demonstrate its efficiency of.We will in this,A simple test on the efficiency of various sorting.

3.6.5.2优化方法三:三数取中法

3.6.5.2.1优化思路

Because of the random selected benchmark method"随机性"过高,Difficult to ensure proper benchmark to.A more commonly used algorithm is"三数取中法". As shown in the following figure arrays, for example,三数取中,指的是left,right,mid三数,其中mid = left+(right-left)>>>1;
As shown in the figure below array,在第一轮排序中,我们会在4,6,8Select the middle number and the size of the current benchmark4交换,也就是选择6与4交换.This is sorted in each,Can be as much as possible, ensure uniform group,避免出现"单分支"的情况,To improve the efficiency of algorithm.
在这里插入图片描述

3.6.5.2.2代码实现

package Sort;
import java.sql.SQLOutput;
import java.util.Arrays;
import java.util.Random;
public class TestSort {

/** * 快速排序 * @param array */
public static void quickSort(int[] array) {

quick(array,0,array.length-1);
}
private static void quick(int[] array, int left, int right) {

if(left >= right) return;
// 1.在某个区间的时候,使用直接插入排序{The comparison of optimal range}
if(right-left+1 <= 5){

//进行插入排序
insertSortRange(array,left,right);
return;
}
// 三数取中法
int index = medianOfThreeIndex(array,left,right);
swap(array,left,index);
int pivot = partitionHole(array,left,right);
quick(array,left,pivot-1);
quick(array,pivot+1,right);
}
private static int medianOfThreeIndex(int[] array, int left, int right) {

int mid = left + ((right-left)>>>1);
//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;
}
}
}
private static void insertSortRange(int[] array, int left, int right) {

for(int i = left+1;i <= right;i++) {

int tmp = array[i];
int j = i-1;
for (; j >= left ; j--) {

if(array[j] > tmp) {

array[j+1] = array[j];
}else {

//array[j+1] = tmp;
break;
}
}
array[j+1] = tmp;
}
}
/* 这是Hole法 */
private static int partitionHole(int[] array, int low, int high) {

int tmp = array[low];
while(low < high){

while(low < high && array[high] >= tmp){

high--;
}
array[low] = array[high];
while(low < high && array[low] <= tmp){

low++;
}
array[high] = array[low];
}
array[low] = tmp;
return low;
}
public static void main(String[] args) {

int[] array = {
2,1,53,4,5,10,9,36,23,6,19};
System.out.println("排序前："+ Arrays.toString(array));
quickSort(array);
System.out.println("排序后："+ Arrays.toString(array));
}
}

在这里插入图片描述

对于"快排"的优化,可以参考这篇文章:
Quick sort of optimizing operation

3.6.4非递归实现快速排序

3.6.4.1基本思路

非递归实现快速排序,Need to use the stack this data structure.需要注意的是,To realize non-recursive quick sort,Must be on the basis of sorting in the round.

在这里插入图片描述
在这里插入图片描述

3.6.4.2代码实现

package Sort;
import java.sql.SQLOutput;
import java.util.Arrays;
import java.util.Random;
import java.util.Stack;
public class TestSort {

/* 这是Hoare法 */
private static int partitionHoare(int[] array, int low, int high) {

//To select the first element in the array as a benchmark for example
//首先,Need to save the first element of the array
int i = low;
int tmp = array[low];
while(low < high){

//1.如果low与highNo cross andhigh下标元素＞=基准值,high--继续找
while(low < high && array[high] >= tmp){

high--;
}
//出循环,说明此时highIs the number of you are looking for
//2.如果low与highNo cross andlow下标元素<=基准值,low++继续找
while(low < high && array[high] <= tmp){

low++;
}
//出循环,说明此时lowIs the number of you are looking for
swap(array,low,high);
}
//出循环,此时low与high相遇,Will meet again in the value of the basic value and exchange
swap(array,low,i);
return low;
}
/** * 非递归实现快速排序 * @param array */
public static void quickSortNor(int[] array){

Stack <Integer> stack = new Stack<>();
int left = 0;
int right = array.length - 1;
//Must be established on the basis of a sort of
int pivot = partitionHoare(array,left,right);
//On the left more than two data,需要入栈
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 = partitionHoare(array,left,right);
//On the left more than two data
if(pivot > left+1){

stack.push(left);
stack.push(pivot-1);
}
if(pivot < right-1){

stack.push(pivot+1);
stack.push(right);
}
}
}
public static void main(String[] args) {

int[] array = {
2,1,53,4,5,10,9,36,23,6,19};
System.out.println("排序前："+ Arrays.toString(array));
quickSortNor(array);
System.out.println("排序后："+ Arrays.toString(array));
}
}

在这里插入图片描述

3.7归并排序

3.7.1基本思想

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为二路归并.

3.7.2图解+步骤

Merge sort is divided into two parts:分解+合并.

在这里插入图片描述

具体步骤如下:

  • 步骤1：把长度为n的输入序列分成两个长度为n/2的子序列;
  • 步骤2：对这两个子序列分别采用归并排序;
  • 步骤3：将两个排序好的子序列合并成一个最终的排序序列.

3.7.3代码实现

package Sort;
import java.sql.SQLOutput;
import java.util.Arrays;
import java.util.Random;
import java.util.Stack;
public class TestSort {

/** * 归并排序 * @param array */
private static void merge(int[] array,int low,int mid,int high) {

int s1 = low;
int e1 = mid;
int s2 = mid+1;
int e2 = high;
int[] tmpArr = new int[high-low+1];
int k = 0;//代表tmpArr的下标
//证明两个段都有数据
while (s1 <= e1 && s2 <= e2) {

if(array[s1] <= array[s2]) {

tmpArr[k++] = array[s1++];
}else {

tmpArr[k++] = array[s2++];
}
}
//剩余元素,全部挪过来
while (s1 <= e1) {

tmpArr[k++] = array[s1++];
}
//剩余元素,全部挪过来
while (s2 <= e2) {

tmpArr[k++] = array[s2++];
}
for (int i = 0; i < tmpArr.length; i++) {

array[i+low] = tmpArr[i];
}
}
private static void mergeSortInternal(int[] array,int low,int high) {

if(low >= high) return;
int mid = low+((high-low)>>>1);
mergeSortInternal(array,low,mid);
mergeSortInternal(array,mid+1,high);
merge(array,low,mid,high);
}
public static void mergeSort(int[] array) {

mergeSortInternal(array,0,array.length-1);
}
public static void main(String[] args) {

int[] array = {
2,1,53,4,5,10,9,36,23,6,19};
System.out.println("排序前："+ Arrays.toString(array));
mergeSort(array);
System.out.println("排序后："+ Arrays.toString(array));
}
}

在这里插入图片描述

3.7.4归并排序的非递归实现

package Sort;
import java.sql.SQLOutput;
import java.util.Arrays;
import java.util.Random;
import java.util.Stack;
public class TestSort {

private static void merge(int[] array,int low,int mid,int high) {

int s1 = low;
int e1 = mid;
int s2 = mid+1;
int e2 = high;
int[] tmpArr = new int[high-low+1];
int k = 0;//代表tmpArr的下标
//证明两个段都有数据
while (s1 <= e1 && s2 <= e2) {

if(array[s1] <= array[s2]) {

tmpArr[k++] = array[s1++];
}else {

tmpArr[k++] = array[s2++];
}
}
//剩余元素,全部挪过来
while (s1 <= e1) {

tmpArr[k++] = array[s1++];
}
//剩余元素,全部挪过来
while (s2 <= e2) {

tmpArr[k++] = array[s2++];
}
for (int i = 0; i < tmpArr.length; i++) {

array[i+low] = tmpArr[i];
}
}
/** * \非递归的归并排序 * @param array */
public static void mergeSortNor(int [] array){

int gap = 1;
while(gap < array.length){

for (int i = 0; i < array.length; i+= 2*gap) {

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,mid,right);
}
gap *= 2;
}
}
public static void main(String[] args) {

int[] array = {
2,1,53,4,5,10,9,36,23,6,19};
System.out.println("排序前："+ Arrays.toString(array));
mergeSortNor(array);
System.out.println("排序后："+ Arrays.toString(array));
}
}

在这里插入图片描述

3.7.5海量数据的排序问题

外部排序：排序过程需要在磁盘等外部存储进行的排序
前提：内存只有 1G,需要排序的数据有 100G
因为内存中因为无法把所有数据全部放下,所以需要外部排序,归并排序是最常用的外部排序.

具体步骤:

  1. 先把文件切分成 200 份,每个 512 M;
  2. 分别对 512 M 排序,因为内存已经可以放的下,所以任意排序方式都可以;
  3. 进行二路归并,同时对 200 份有序文件做归并过程,最终结果就有序了.

图解:
在这里插入图片描述

3.7.6总结

  1. 时间复杂度：N*logN(和数据是否有序没有关系)
  2. 空间复杂度：O(N),At most one openingN大小的空间.
  3. 稳定性：稳定

四:Based on the comparison of sorting summary

在这里插入图片描述
在这里插入图片描述

The above order is based on the comparison of sorts.接下来,I will introduce three kind of based on the comparison of sequence.

五:非基于比较的排序

5.1计数排序

5.1.1基本思想

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

What is the principle of dove nest?简单来说就是,桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,我们会发现至少会有一个抽屉里面放不少于两个苹果.这一现象就是我们所说的“抽屉原理”. 抽屉原理的一般含义为：“如果每个抽屉代表一个集合,每一个苹果就可以代表一个元素,假如有n+1个元素放到n个集合中去,其中必定有一个集合里至少有两个元素.” 抽屉原理有时也被称为鸽巢原理.它是组合数学中一个重要的原理.

5.1.2图解+步骤

在这里插入图片描述
基本步骤是:

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

注意

  • 在实际排序中,Don't always to meet like0~9So reveals the human nature brilliant subject.一种情况是,We need to count90-99之间的数据,Currently we will not apply to the array size for100的空间,而是将90This element is the number of occurrences of record in0下标位置,91This element is the number of occurrences of record in1下标位置,依次类推即可.Only when the print will need to the corresponding subscript plus the offset can be.
  • Another situation is more common,Such as we need to count the data is not closely aligned,But there is no rule,如下图所示:
    在这里插入图片描述
    This kind of situation will need to first calculate the data of the maximum and the minimum,But the amount of the array size is[最大值-最小值+1].不难发现,There are a lot of space will be wasted at this time,这也说明,计数排序的时间复杂度andSpace complexity is closely related to the scope of data sorting,I will be in the back of the summary about this problem.

5.1.3代码实现

package Sort;
import java.sql.SQLOutput;
import java.util.Arrays;
import java.util.Random;
import java.util.Stack;
public class TestSort {

/** * 计数排序 * @param array */
public static void countSort(int [] array) {

int min = array[0];
int max = array[0];
for (int i = 1; i < array.length; i++) {

if(min > array[i]){

min = array[i];
}
if(max < array[i]){

max = array[i];
}
}
//此时min和maxRespectively is the maximum and the minimum of data
int[] arr = new int[max-min+1];
for (int i = 0; i < array.length; i++) {

arr[array[i]-min]++;
}
int k = 0;
for (int i = 0; i < arr.length; i++) {

int count = arr[i];
while(count-- != 0){

array[k++] = (i+min);
}
}
}
public static void main(String[] args) {

int[] array = {
2,1,53,4,5,10,9,36,23,6,19};
System.out.println("排序前："+ Arrays.toString(array));
countSort(array);
System.out.println("排序后："+ Arrays.toString(array));
}
}

在这里插入图片描述

5.1.4总结

  1. 时间复杂度:O(范围+N);
  2. 空间复杂度:O(范围);
  3. 稳定性:稳定

注意
Although I have written you code is can guarantee the stability of,但是我们可以通过一些方法,The result of quick sort is stable.具体操作如下:
在这里插入图片描述
在这里插入图片描述

5.2基数排序

5.2.1基本思想

Radix sort in count sorting is improved on the basis of,将排序工作拆分为多个阶段,Sort the integer data, for example,Every stage only according to a digital sorting,一共排序K轮(K为数据位数).

5.2.2图解+步骤

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

5.3桶排序

5.3.1基本思想

Bucket sort is similar to radix sort,,不同之处在于,When the bucket sort is could be divided into different interval data,在每个区间(桶)After the data sorted,Again, in turn, out of the barrel,Back in the original sequence.

5.3.2图解+步骤

在这里插入图片描述
步骤:

  1. According to the scope of the sorting data before,Sure need the number of barrels;
  2. All the data into the barrel inside,Inside the bucket sort;
  3. All the data in turn out of the barrel,All data can be realized in order.

六:All the sorting algorithm to summarize

在这里插入图片描述
Above is all the sorting algorithm!
We must master7More sort of idea and code,For three of comparative sequence,Only need to master the basic idea can be.重在理解,及时复盘,才能事半功倍!!

copyright：author[Knowing & Doing]，Please bring the original link to reprint, thank you. https://en.javamana.com/2022/218/202208061752468121.html

《 JAVA based - 11 - encapsulated inherited polymorphism - nine five small jean-marie le pen