排序算法总结及java实现

前面三篇博文分别实现了快速排序：排序算法之快速排序java实现、堆排序：排序算法之堆排序java实现和归并排序：排序算法之归并排序java实现。

本篇博文主要分析常用的几种排序算法。

首先来看一下各个排序算法的复杂度，如下图所示（图片来自百度图片）

1、插入排序

插入排序（Insert Sort），每步将一个待排序的对象，按其排序码大小，茶如道前面已经排好序的一组对象的适当位置上个，直到对象全部插入为止。根据插入点查找方式的不同，有这样几个方法：直接插入排序、折半插入排序、希尔排序。

1）直接插入排序（稳定）

直接插入排序的基本思想是：顺序地把待排序的数据元素按其值的大小 插入到已排序数据元素子集合的适当位置，直到子集合大小和集合大小相同时为止。

直接插入排序过程如下图所示（图片来自百度图片）：

直接插入排序java实现：

package sort;

public class InsertSort {

public static void main(String[] args) {

int[] a = {53, 27, 36, 15, 69, 42};
d_insertSort(a);
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}

}

public static void d_insertSort(int[] a){  //直接插入排序
for(int i=1; i<a.length; i++){
int j = i-1;
int key = a[i];
while(j>=0 && a[j]>key){
a[j+1] = a[j];
j--;
}
a[j+1] = key;
}
}
}

输出：15 27 36 42 53 69 

2）希尔（Shell）排序（不稳定）

希尔排序的基本思想是：把待排序的数据元素分成若干个小组，对同一小组内的数据元素用直接插入法排序；小组的个数逐次缩小；当完成了所有数据元素都在一个组内的排序后排序过程结束。希尔排序又称缩小增量排序。
希尔排序过程如下图所示（图片来自百度图片）：

希尔排序java实现（略）

2、选择排序

1）直接选择排序（不稳定）

直接选择排序的算法思想是：首先找到最小元素，将其放入a[0]中，然后找到剩下的n-1个元素中最小元素，将其放入a[1]中，重复此过程，直到找到第二大元素，将其放入a[n-2]中。
直接选择排序过程如下图所示：

直接选择排序java实现：

package sort;

public class SelectionSort {

public static void main(String[] args) {

int[] a = {53, 27, 36, 15, 69, 42};
d_selectionSort(a);
for(int i=0; i<a.length; i++){
System.out.print(a[i] + " ");
}
}

public static void d_selectionSort(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[j] < a[k])
k = j;
}
if(k!=i){//交换
int temp = a[i];
a[i] = a[k];
a[k] = temp;
}
}
}

}

输出：15 27 36 42 53 69 

2）堆排序（不稳定）

堆排序在前面的一篇博文中以详细介绍：排序算法之堆排序java实现，这里不再重复。

3、交换排序

1）冒泡排序（稳定）

冒泡排序的基本思想是：设数组a中存放了n个元素，循环进行n-1趟如下排序过程：第1趟时，依次比较相邻两个数据元素a[i]和a[i+1](i=0,1,2,...,n-2)，若为逆序，则交换两个元素，否则不交换，这样数组最大的数据元素将被放在a[n-1]中。第二趟时，循环次数减1，操作步骤和第一趟类似，如此循环重复，直到a[0]放置最小的元素。就像水底的气泡一样逐渐向上冒。
冒泡排序过程如下图所示（网络图片）：
冒泡排序java实现：

package sort;

public class BubbleSort {

public static void main(String[] args) {

int[] a = {53, 27, 36, 15, 69, 42};
bubbleSort(a);
for(int i=0; i<a.length; i++){
System.out.print(a[i] + " ");
}
}

static void bubbleSort(int[] a){
for(int i=0; i<a.length-1; i++){  //n-1趟排序
for(int j=0; j<a.length-i-1; j++){  //对无序序列0~length-i-1进行排序

if(a[j]>a[j+1]){
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}

}

输出：15 27 36 42 53 69 

2）快速排序（不稳定）

快速排序在前面的一篇博文中已详细描述：排序算法之快速排序java实现，这里不再重复

归并排序（稳定）：排序算法之归并排序java实现