前言：本期穿插讲解一些《算法与数据结构系列》（Algorithms and Data Structures，题中简称AD），此篇为第一期——排序算法。
插入排序
插入排序法的思想是从前往后，先排序前两个元素，把第三个元素插入其中，然后让前三个已经排好序，再把第四个插入前三个中，排好序...以此类推，直到最后一个插入为止，这样便完成了插入排序。该算法的复杂度为n^2。
public class InsertSort {
public static void main(String[] args)
{
//数组声明
int[] a = {5,1,3,0,1,4,-1};
int L = a.length;
//首先确保前两个元素是升序的
if(a[1]<a[0])
{
int tmp=a[0];
a[0]=a[1];
a[1]=tmp;
}
//其次进行插入排序
for(int i=2;i<L;i++)
{
//如果待插入的数小于或等于已排序的表头
if(a[i]<=a[0])
{
int tmp=a[i];
for(int j=i;j>0;j--)
{
a[j]=a[j-1];
}
a[0]=tmp;
}
//如果待插入的数大于或等于已排序的表尾
else if(a[i]>=a[i-1])
continue;
//如果待插入的数介于已排序的表中某两个数中间
else
{
for(int k=0;k<i-1;k++)
{
if(a[i]>=a[k]&&a[i]<=a[k+1])
{
int tmp1=a[i];
for(int m=i;m>k+1;m--)
{
a[m]=a[m-1];
}
a[k+1]=tmp1;
}
}
}
}
for(int element:a)
System.out.println(element+" ");
}
}
堆排序
堆排序的思想是，首先需要构造一个堆的数据结构，我们说程序=数据结构+设计模式，因此好的数据结构对程序具有至关重要的作用，堆是一种完全二叉树，父节点大于子节点，依据根节点是最大值这一重要特性，然后依次从根节点取出元素，使得堆依次重构，最后，即可完成排序。该算法复杂度为nlogn。
import java.util.*;
/*
* 本程序是进行堆排序
* 首先需要明白堆是一种特殊的完全二叉树，并且它的孩子结点永远小于父母结点
*/
public class HeapSort<E extends Comparable> {
public static void main(String[] args) {
//声明一个列表，存储数据
Integer[]list={1,0,-2,3,5,1,2,10,11,21,3,2};
heapsort(list);
for(Integer element:list)
System.out.println(element);
}
/*
* 首先编写堆类
* 堆类用线性列表来存储数据
*
* */
private ArrayList<E> list=new ArrayList<E>();
public HeapSort(E[] objects)
{
for(int i=0;i<objects.length;i++)
add(objects[i]);
}
public HeapSort() {
}
public void add(E object)
{
list.add(object);
int currentindex=list.size()-1;
while(currentindex>0)
{
int parentindex=(currentindex-1)/2;
/*
* 如果父类结点小于子类结点，则将它们交换值
* 这个过程一直持续到父类结点不再小于子类结点为止
*/
if(list.get(parentindex).compareTo(list.get(currentindex))<0)
{
E temp=list.get(currentindex);
list.set(currentindex, list.get(parentindex));
list.set(parentindex, temp);
}
else
break;
currentindex=parentindex;//把新加的数的下标更新
}
}
@SuppressWarnings("unchecked")
public E remove()
{
if(list.size()==0)
return null;
/*
* 基本思想是
* remove()方法只能移除根处的元素
* 然后重新组建堆
* 首先把最后一个元素移到根处
* 然后将根与它的结点进行比较，若小于其子结点，则交换下移即可
* 直到下标最大为止
*/
E removedObject=list.get(0);
list.set(0, list.get(list.size()-1));
list.remove(list.size()-1);
int currentindex=0;
while(currentindex<list.size())
{
int leftchildindex=2*currentindex+1;//左孩子
int rightchildindex=2*currentindex+2;//右孩子
if(leftchildindex>=list.size())
break;
/*
* 下面语句确定左边子结点与右边子结点的大小
* 以便将父结点与最大的子结点进行比较
* 进而确定是否执行交换动作
*/
int maxindex=leftchildindex;
if(rightchildindex<list.size())
{
if(list.get(maxindex).compareTo(list.get(rightchildindex))<0)
maxindex=rightchildindex;
}
/*
* 下面开始执行交换动作
* 若父结点比最大的子结点要小
* 则交换它们
*/
if(list.get(currentindex).compareTo(list.get(maxindex))<0)
{
E temp=list.get(currentindex);
list.set(currentindex, list.get(maxindex));
list.set(maxindex, temp);
currentindex=maxindex;
}
/*
* 直到父结点不再小于最大的子结点为止
*/
else
break;
}
return removedObject;
}
public static <E extends Comparable>void heapsort(E[]list)
{
HeapSort<E> heap=new HeapSort<E>();
for(int i=0;i<list.length;i++)
heap.add(list[i]);
for(int i=list.length-1;i>=0;i--)
list[i]=heap.remove();
}
}
归并排序
归并排序的思想源自分而治之，即把一个大任务分割成两个小任务，再递归分割，直到不能分割为止。对于一个数组，我们可以将其分成两部分，再将各小部分分别分成两部分，最后使得数组分成N份，N为元素总数，再两两按大小合并，四四按大小合并...直到最后合并完整为止，即可完成排序。该算法复杂度为nlogn。
public class MergeSort {
//归并排序，首选采用分而治之的思想，运用递归方法，将数组分组两半
public static void guibing(int[] list)
{
int L=list.length;
//将数组递归分成两部分
if(L>1)
{
//第一部分为前一半元素
int[] firstHalf=new int[L/2];
//调用arrayCopy方法，将list中的前一半元素复制到firstHalf之中
System.arraycopy(list, 0, firstHalf, 0, L/2);
//递归：将这个子数组再分成两半
guibing(firstHalf);
//第二部分为后一半元素（不一定与第一部分元素个数相同）
int[] secondHalf=new int[L-L/2];
//调用arrayCopy方法，将list中的后一半元素复制到secondHalf之中
System.arraycopy(list, L/2, secondHalf, 0, secondHalf.length);
//递归：将这个子数组再分成两半
guibing(secondHalf);
//一旦所有的递归拆分都已经结束，那么进行归并
int[]temp=merge(firstHalf,secondHalf);
//将temp数组的所有元素复制到list之中
//参数的含义：源数组，首索引，目标数组，首索引，复制长度
System.arraycopy(temp, 0, list, 0, temp.length);
}
}
//归并两个数组
//因为两个数组已经是排序的，所以只需依次比较两个元素的对应值即可，"谁小就谁上"
private static int[] merge(int[] list1,int[] list2)
{
//声明最终数组及长度
int[] tmp=new int[list1.length+list2.length];
//设置索引量初始化
int current1=0,current2=0,current3=0;
//当两个子数组均没有结束，需要比较它们的值
while(current1<list1.length&¤t2<list2.length)
{
if(list1[current1]<list2[current2])
tmp[current3++]=list1[current1++];
else
tmp[current3++]=list2[current2++];
}
//如果只剩下第一个子数组了，就直接把剩下的元素依次放入最终数组之中
while(current1<list1.length)
tmp[current3++]=list1[current1++];
//如果只剩下第二个子数组了，就直接把剩下的元素依次放入最终数组之中
while(current2<list2.length)
tmp[current3++]=list2[current2++];
//至此，合并结束，返回最终数组
return tmp;
}
public static void main(String[] args) {
//首先声明数组
int[]a={-5,1,3,2,1,0,2,-2,0};
int L=a.length;
//归并排序
guibing(a);
//输出结果
for(int element:a)
System.out.println(element);
}
}
快速排序
快速排序算法的思想其实也是来自分治法，不过除了这个之外，还是用了定与不定的思想，即我在分割任务的同时，每一步都可以寻找一个定的元素，即找主元的位置。主元的位置一旦确定，即不会改变，而将N个元素两两分割直到不能分割为止，运用递归的思想，在每一小块中都寻找主元的位置。最终完成了快速排序。该算法复杂度为nlogn。
/*
* @快速排序法
*/
public class QuickSort {
//快速排序主程序
public static void sort(int[] arr)
{
quickSort(arr,0,arr.length-1);
}
//快速排序法递归，表明要排序的数组，以及起始索引
private static void quickSort(int[]arr,int first,int last)
{
//只要最后一个大于第一个的索引
if(last>first)
{
//将数组分为两部分，并且选择第一个为主元
int pivotIndex=partition(arr,first,last);
//对主元分开的两个子数组进行排序
quickSort(arr,first,pivotIndex-1);
quickSort(arr,pivotIndex+1,last);
}
}
//寻找主元并且划分数组的部分
public static int partition(int[] list,int first,int last)//划分数组为两部分
{
//选择第一个为主元
int pivot=list[first];
//后面将数组划分为大于主元和小于主元的两大块
int low=first+1;
int high=last;
//如果high大于low
while(high>low)
{
//如果low的元素小于pivot就继续推进
while(low<=high&&list[low]<=pivot)
low++;
//如果high的元素大于pivot就继续后退
while(low<=high&&list[high]>pivot)
high--;
//否则，说明出现了相反情况，则交换两个元素
if(high>low)//当list[high]<list[low]时，就交换二者
{
int temp=list[high];
list[high]=list[low];
list[low]=temp;
}
}
while(high>first&&list[high]>=pivot)
high--;
//如果一开始选的主元比最后一个high元素要大
if(pivot>list[high])
{
list[first]=list[high];
list[high]=pivot;
return high;
}
else
return first;
}
public static void main(String[] args) {
//声明数组
int[]arr={1,2,3,0,1,5,-1,2};
//调用快速排序算法
sort(arr);
//输出结果
for(int element:arr)
System.out.println(element);
}
}
冒泡排序
冒泡排序估计是最为熟悉的，也是最好写的，它的思想是每一次遍历都会两两比较，比如说从最后一个元素往前遍历的话，遇到比自己大的就交换过来，于是，这样最后的话，相当于小的元素都浮上来了，形象地称为冒泡法，一共最多需遍历n趟，当然如果某一次遍历发现什么动作也没有，说明排序已经完成了。该算法复杂度为n^2。
public class BubbleSort {
public static void main(String[] args)
{
//声明数组
int[]a={-5,1,3,2,1,0,2,-2};
int L=a.length;
//声明临时变量
int tmp;
int Flag=0;
//若某次遍历中Flag的值保持为1，则说明排序已经完成，可以退出了
while(Flag==0)
{
Flag=1;
for(int i=0;i<L-1;i++)
{
//交换相邻元素
if(a[i]>a[i+1])
{
tmp=a[i];
a[i]=a[i+1];
a[i+1]=tmp;
Flag=0;
}
}
}
//输出结果
for(int element:a)
System.out.println(element);
}
}
选择排序
选择排序算法的思想也很简单，先假设第一个数为最小数，作为基准，然后依次向后轮询，遇到比最小的数还要小，就替换掉，一趟过后，第一个数就确定了，接下来以此类推，将第二个数确定下来......该算法复杂度为n^2.
public class SelectSort {
public static void main(String[] args)
{
//首先声明数组
int a[]={-5,1,3,2,1,0,2,-2};
int L=a.length;
//找到最小的数，依次放到表头...
for(int i=0;i<L;i++)
{
//找出最小的数
for(int j=i+1;j<L;j++)
{
if(a[j]<a[i])
{
int T=a[j];
a[j]=a[i];
a[i]=T;
}
}
}
//输出结果
for(int element:a)
System.out.println(element);
}
}
最后分享摘自余秋雨《千年一叹》一书中的名句：
金字塔至今不肯坦示为什么要如此永久，却透露了永久是什么。
来源：张泽旺 深度学习每日摘要
智造家