<h2>前沿：排序算法想必是日常编程中最常用编程技能之一了吧？不知道有多少人和我一样接触的第一个算法就是冒泡排序。笔者将在这里分别介绍选择排序，插入排序，希尔排序，归并排序，快速排序。我认为这些排序算法都是为了改良前者其时间复杂度或空间复杂度而循序渐进的，所以我将用我的理解尽可能通俗易懂的介绍这5种排序算法。</h2>
<h3>开始介绍算法之前还是先把排序模板类的代码贴一下，里面包括一些简单的函数,我们后续排序算法继承此模板类。</h3>
<pre>
package com.example.sort;
/**
* 插入排序算法
* */
public abstract class SortTamplate {
public abstract void sort(Comparable a[]);
//比较两个数的大小
public static boolean less(Comparable v,Comparable w){
return v.compareTo(w) < 0;
}
//交换两个数
public static void exchange(Comparable a[],int i,int j){
Comparable temp = a[i];
a[i] = a[j];
a[j] = temp;
}
//打印数组
public static void show(Comparable a[]){
for(int i=0;i<a.length;i++){
System.out.print(a[i]+",");
}
}
//数组是否有序
public static boolean isSort(Comparable a[]){
for(int i=1;i<a.length;i++){
if(less(a[i],a[i-1])){
return false;
}
}
return false;
}
}
</pre>
<h4>首先介绍的就是-选择排序</h4>
<blockquote>选择排序即每次遍历数组选择数组中最小的(或者最大的)数，将其置于数组最前面,逻辑很简单，就不做多解释了，还是直接上代码好了。</blockquote>
<pre>
package com.example.sort;
/**
* 选择排序算法
* */
public class Selection extends SortTamplate{
public void sort(Comparable a[]){
long begin = System.currentTimeMillis();
int N = a.length;
for(int i=0;i<N;i++){
//最小数索引
int min = i;
//循环找出数组中最小的数的索引
for(int j=i+1;j<N;j++){
if(less(a[j],a[min])){
min = j;
}
}
//将最小数索引置于数组前面
exchange(a,i,min);
}
long end = System.currentTimeMillis();
System.out.println("算法用时："+(end-begin));
}
}
</pre>
<h6>可以从代码很直观的看出选择排序需要N²/2次比较和N次交换，时间复杂度为0(n²)。其每次扫描出最小数对于下一次扫描未提供任何信息，所以对于一个有序或者部分有序的数组和完全无序数组来说，所需的时间复杂度是完全相等的。所以，就引出了下一个排序算法，插入排序。</h6>
<blockquote>
插入排序：顾名思义，往一个有序数组中添加一个数时，只需将这个数插入到数组中适当的位置即可。插入排序利用这一点，比较前1到n长度的数组，这样做的目的是使每次比较都为后一次比较提供一个有序的子数组，后一个数只需插入到前一个子数组中。
</blockquote>
<pre>
package com.example.sort;
/**
* 插入排序
* */
public class Insertion extends SortTamplate{
public void sort(Comparable a[]){
}
public static void sort(Comparable a[],int low,int high){
long begin = System.currentTimeMillis();
int N = a.length;
for(int i= 0;i<N;i++){
for(int j=i;j>0 && less(a[j],a[j-1]);j--){//重点为此处循环终止条件
exchange(a,j,j-1);
}
}
long end = System.currentTimeMillis();
System.out.println("算法用时："+(end-begin));
}
}
</pre>
<h6>所以插入排序非常适合部分有序数组或者小规模数组。然而对于大规模的乱序数组插入排序很慢，因为它只交换相邻的元素，因此元素只能一点一点地从一端移动到另一端。接下来就介绍一种基于插入排序的快速的排序算法——希尔排序。</h6>
<blockquote>
希尔排序：希尔排序为了加快速度简单的改进了插入排序，交换不相邻的元素对数组的局部进行排序，并最终用插入排序对于局部有序数组进行排序。
<strong>希尔排序的思想是使数组中任意间隔为H的数组有序。换句话说，一个有序数组，是由h个互相独立的有序数组组成，在进行排序时，如果h很大，我们就能将元素移动到很远的地方，为实现更小的h有序创造方便。用这种方式，对于任意以1结尾的序列，我们都能够将数组排序。这就是希尔排序。
为方便理解，我自制了一张排序轨迹图。</strong>
</blockquote>
shell.png
<pre>
package com.example.sort;
/**
* 希尔排序
* */
public class ShellSort extends SortTamplate{
public void sort(Comparable a[]){
long begin = System.currentTimeMillis();
int N = a.length;
int h = 1;
while(h<N/3){
h = h*3 + 1;
}
while(h >= 1){
for(int i = h;i<N ;i++){
for(int j=i;j>=h && less(a[j],a[j-h]);j=j-h){
exchange(a,j,j-h);
}
}
h = h/3;
}
long end = System.currentTimeMillis();
System.out.println("算法用时："+(end-begin));
}
}
</pre>
<h6>对于h间隔步长的选择建议使用序列1，4，13，40，121···有排序轨迹图可知，希尔排序比插入排序时间复杂度有低很多，且数组规模越大，效率越明显。在排序(下)中，我将介绍更加高效的算法。</h6>
网友评论