简单选择排序
对于长度为n的数组a
- 找出后n个数（下标0~n-1）中最小的数，与a[0]交换
- 找出后n-1个数（下标1~n-1）中最小的数，与a[1]交换
- 找出后n-2个数（下标2~n-1）中最小的数，与a[2]交换
-
依次类推
即每次找到剩余数组中最小的元素放在前面，代码如下：
/**
* 简单选择排序，O（n^2）
* @param a
*/
public static void selectSort(int[] a) {
for (int i = 0; i < a.length-1; i++) {
int k=i; //剩余数组中最小元素下标
for (int j = i+1; j < a.length; j++) {
if(a[k]>a[j])
k=j;
}
//交换a[k]与a[i]
swap(a, k, i);
}
}
冒泡排序
对于长度为n的数组a
- 对前n个数进行冒泡式交换（从0到n-1，如果相邻的两个数，a[i]>a[i+1]则交换），最后使a[n-1]为前n个数中最大数
- 对前n-1个数进行冒泡式交换，最后使a[n-2]为前n-1个数中最大数
- 对前n-2个数进行冒泡式交换，最后使a[n-3]为前n-2个数中最大数
-
依次类推
即每次找出最大的数放在后面，与选择排序相反。代码如下：
/**
* 冒泡排序，O（n^2）
* @param a
*/
public static void bubbleSort(int[] a) {
for (int i = 0; i < a.length; i++) {
//一次排序后使尾部的数为最大的
for (int j = 0; j < a.length-i-1; j++) {
if(a[j]>a[j+1]){
swap(a, j, j+1);
}
}
}
}
插入排序
对于无序序列，假设前i个数为有序的，将第i+1个数插入前i个数中，使其成为i+1个有序序列。
如图，对于长度为n的数组a
- 前1个数为有序序列，将a[1]插入其中，形成2个数的有序序列
- 前2个数为有序序列，将a[2]插入其中，形成3个数的有序序列
-
依次类推，最终前n个数都变成有序序列，排序成功
代码如下：
/**
* 插入排序，O（n^2）
* @param a
*/
public static void insertSort(int[] a) {
int temp,j;
//将a[i]插入前面的有序序列中
for (int i = 1; i < a.length; i++) {
temp=a[i];
//从有序序列尾部递减，如果比a[i]大则向后放置
for (j=i-1; j >=0&&a[j]>temp; j--) {
a[j+1]=a[j];
}
//将a[i]插入有序序列
a[j+1]=temp;
}
}
快速排序
稍微复杂点的算法，运用了“分治”的思想
对于无序序列，随便找出其中一个数作为“基准数”，然后将序列中小于它的数放在其左边，大于它的数放在它右边。再对左右区间重复此过程，直到区间只有一个数，排序成功。具体过程如下图：
过程很好理解，但难点在于如何实现这个左右区间呢?
我们设置两个变量i和j，分别指向序列的头和尾。让i递增，j递减。每次找到比基准数大的a[i]和比基准数小的a[j]后便进行交换。一直到i=j，再最后一次交换基准数与a[j]。此时便实现了一个基准数左边比它小，右边比它大的序列。
需要注意的是，每次必须是j先递减。原因是这样最后一次交换时，保证基准数交换的是比它小的a[j]。
没有画图来讲述整个过程，还是不懂可以看：坐在马桶上看算法：快速排序
下面是代码：
/**
* 快速排序,O(nlogn)
* @param a
* @param left
* @param right
*/
public static void quickSort(int[] a, int left, int right) {
if (left > right)
return;
int middle = a[left]; // 基准数
int i = left;
int j = right;
while (i != j) {
// 从最右递减找出小于基准数的数
while (a[j] >= middle && i < j) {
j--;
}
// 从最左递增找出大于基准数的数
while (a[i] <= middle && i < j) {
i++;
}
// 交换
swap(a, i, j);
}
// 将基准数和最后小于它的数进行交换
a[left] = a[i];
a[i] = middle;
// 以基准数划分左右区间，再对左右区间进行快排
quickSort2(a, left, i - 1);
quickSort2(a, i + 1, right);
}
由于a[left]我们已经用middle保存了，所以也可以利用a[left]来作为中间变量交换a[i]和a[j]，优化后的代码如下：
/**
* 快速排序，O(nlogn)
* @param a
* @param left
* @param right
*/
public static void quickSort(int[] a,int left,int right) {
if(left>right)
return ;
int middle=a[left]; //基准数
int i=left;
int j=right;
while (i != j) {
//从最右递减找出小于基准数的数
while (a[j] >= middle && i < j) {
j--;
}
a[i]=a[j];
//从最左递增找出大于基准数的数
while (a[i] <= middle && i < j) {
i++;
}
a[j]=a[i];
}
//将基准数和最后小于它的数进行交换
a[i]=middle;
//以基准数划分左右区间，再对左右区间进行快排
quickSort(a, left, i-1);
quickSort(a, i+1, right);
}
堆排序
堆
堆其实就是一个完全二叉树，分为最大堆（父结点>=子结点）、最小堆（父结点<=子结点）。一般用数组来存储，i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2i + 1和2i + 2。
堆的两个操作
要明白堆排序，就要先明白堆的添加和删除原理。
- 在堆数组尾部添加元素时，需要不停将该元素与其父结点进行对比交换，类似于元素在“上升”。也就是使新添加的元素插入一个有序的序列中，形成一个新的有序堆序列
- 堆删除元素时，总是先删除根结点，然后将最后一个元素移到根结点，与子结点对比交换，类似于元素在“下沉”。最终形成新的有序堆序列。
好的，明白堆的添加删除后，我们就可以解决以下问题：
- 现在给了一个无序数组，如何将其变成堆数组？
我们可以对数组反向迭代，从末尾开始每个元素进行“下沉处理”，这样便保证迭代完成后的数组是一个最小堆 - 如何利用堆进行排序
由于最小堆的根结点永远是所有元素中最小的。我们可以进行删除操作。依次取出顶点的结点，这些取出的顶点最终就形成了一个递增序列。
堆排序代码
注意：下面代码为了方便，每次取出堆的顶点放入数组末尾，最终形成了一个递减序列。也可以将取出的元素新放入另外一个数组，形成递增序列。
public class Heap {
private int[] a; //堆数组
private int n; //结点个数
/**
* 构造一个堆化数组
* @param a 数组
* @param n 数组中元素个数
*/
public Heap(int[] a,int n) {
this.a = a;
this.n=n;
for (int i = (n-2)/2; i >=0; i--) {
minHeapDown(i,n);
}
}
/**
* 最小堆，对index下标结点进行“上浮”处理
* @param index
*/
public void minHeapFixUp(int index) {
int temp=a[index];
//index的父结点
int fIndex=(index-1)/2;
//未到顶点时继续
while(fIndex>=0&&index>0){
//如果该结点大于父结点，直接退出循环
if(a[fIndex]<temp)
break;
//如果该结点小于父节点，则交换结点
a[index]=a[fIndex];
index=fIndex;
fIndex=(index-1)/2;
}
a[index]=temp;
}
/**
* 最小堆，对index下标结点进行“下沉”处理
* @param index
* @param n 堆中元素个数
*/
public void minHeapDown(int index,int n) {
int temp=a[index];
int sIndex=2*index+2; //子结点下标为2*index+1、2*index+2
while(sIndex<=n-1){
//找出左右子结点中最小的一个
sIndex=(a[sIndex]>a[sIndex-1])?sIndex-1:sIndex;
//如果子结点比该结点大，退出循环
if(a[sIndex]>temp)
break;
//如果子节点比该结点小，进行交换
a[index]=a[sIndex];
index=sIndex;
sIndex=2*index+1;
}
a[index]=temp;
}
/**
* 新添加一个结点在堆的下标index
* @param index
* @param content
*/
public void add(int index,int content) {
a[index]=content;
minHeapFixUp(index);
}
/**
* 堆的删除操作，即删除头结点
*/
public void remove() {
Sort.swap(a, 0, n-1);
minHeapDown(0,n);
}
/**
* 堆排序，,O(nlogn)
*/
public void minHeapSort(){
for (int i = n-1; i >=1; i--) {
Sort.swap(a, 0, i);
minHeapDown(0,i);
}
}
public static void main(String[] args) {
int[] a={8,9,6,4,7,5,3,4,1};
Heap heap=new Heap(a, a.length);
heap.minHeapSort();
System.out.println(Arrays.toString(a));
}
}/**output:
[9, 8, 7, 6, 5, 4, 4, 3, 1]
*/
几种排序算法时间复杂度的比较
排序算法严格来说没有最快，各有各的适用环境。
如果非要找出一个最快，笔者通过上网查资料，发现大多都推荐的是桶排序。
参考
排序（本文图片出自此网站）
白话经典算法系列之七 堆与堆排序
网友评论