8 つの並べ替えアルゴリズムの実践

ソートアルゴリズムに関しては、最近はあまり使われていませんが、基本的には使用されており、深く理解するために時間を割いたことはありません。最近、理解を深めるために自分でも書いてみることにしました。たくさんの情報を確認しましたが、その多くは非常によく分析されており、すぐに理解することができました。ありがとうございます。

1. 概念的な理解と実装

package com.demo.algorithm.sort;
/**
 * 排序算法合集
 * @author sheungxin
 *
 */
public class NumberSort {
/**
* 插入排序-直接插入排序
* 工作原理：构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入
* 参考：http://blog.csdn.net/morewindows/article/details/6665714
* @param array
* @param asc 0:升序  1:降序
*/
public static void straightInsertSort(int[] array,int asc){
int tmp,n;
//从第二位元素开始，第一位认为已被排序
for(int m=1;m<array.length;m++){
tmp=array[m];
//在已排序序列中从后向前扫描,若该元素>(<)新元素，将该新元素向后移一位
for(n=m-1;n>=0&&(asc==1&&tmp>array[n]||asc==0&&tmp<array[n]);n--){
array[n+1]=array[n];
}
//上述循环在该元素<=(>=)新元素或者扫描到首位时结束,将该元素插入在结束位置后面
array[n+1]=tmp;
}
display(array);
}
/**
* 插入排序-希尔排序，实质就是分组排序，又称缩小增量排序
* 工作原理：先将整个待排序元素序列分割成若干个子序列(由相隔某个“增量”元素组成)分别进行直接插入排序，
*     然后依次缩减增量再进行排序，待整个序列中元素基本有序(增量足够小)时，再进行一次全元素直接插入排序。
* 优势：直接插入排序在元素基本有序的情况下，效率最高
* 参考：http://blog.csdn.net/morewindows/article/details/6668714
* @param array
* @param asc 0:升序  1:降序
*/
public static void shellSort(int[] array,int asc){
int len=array.length;
//依次缩减增量，直到增量为1
for(int gap=len/2;gap>0;gap/=2){
//根据步长把待排序元素分为gap组
for(int i=0;i<gap;i++){
//分别对每组元素进行直接插入排序，从i开始以增加gap得到一组元素
for(int j=i+gap;j<len;j+=gap){
int tmp=array[j];
int k=j-gap;//上一个节点
//在已排序序列中从后向前扫描,若该元素>(<)新元素，将该新元素向后移一位
while(k>=0&&(asc==1&&tmp>array[k]||asc==0&&tmp<array[k])){
array[k+gap]=array[k];
k-=gap;//向前扫描，移到下标
}
//上述循环在该元素<=(>=)新元素或者扫描到首位时结束,将该元素插入在结束位置后面
array[k+gap]=tmp;
}
}
}
   display(array);
}
/**
* 选择排序：简单选择排序
* 原理：从无序区中选择一个最小的元素之间放到有序区的最后
* 参考：http://blog.csdn.net/morewindows/article/details/6671824
* @param array
* @param asc 0:升序  1:降序
*/
public static void selectSort(int[] array,int asc){
int tmp,ix;
for(int i=0;i<array.length;i++){
ix=i;//最小或最大元素的位置
//从无序区中选择一个最小或最大的元素的位置
for(int j=i+1;j<array.length;j++){
if((asc==0&&array[ix]>array[j])||(asc==1&&array[ix]<array[j])){
ix=j;
}
}
//交换位置
if(ix!=i){
tmp=array[i];
array[i]=array[ix];
array[ix]=tmp;
}
}
display(array);
}
/**
* 选择排序：堆排序
* 原理：二叉堆近似二叉树，父节点总是大于或等于(小于或等于)任何一个子节点
* 参考：http://blog.csdn.net/morewindows/article/details/6709644
*    http://blog.csdn.net/kimylrong/article/details/17150475
* @param array
* @param asc 0:升序  1:降序
*/
public static void heapSort(int[] array,int asc){
//构建二叉堆，从最后一个父节点开始
for(int i=array.length/2-1;i>=0;i--){
buildHeap(array, array.length, i, asc);
}
//使用堆根节点构建有序序列
for(int i=array.length-1;i>=1;i--){
//依次把根节点向后交换构建有序序列
swapArray(array, 0, i);
//根节点交换位置后，从0，i-1重新构建堆
buildHeap(array, i, 0, asc);
}
display(array);
}
/**
* 构建二叉堆
* @param array 二叉堆数组
* @param heapSize 二叉堆大小
* @param index 当前父节点位置
* @param asc 0:升序  1:降序
*/
private static void buildHeap(int[] array,int heapSize,int index,int asc){
//比较父节点、左右叶子节点，找出最大或最小节点位置
int left = index * 2 + 1;  
        int right = index * 2 + 2; 
int ix=index;
if(left<heapSize&&(asc==1&&array[index]>array[left]||asc==0&&array[index]<array[left])){
ix=left;
}
if(right<heapSize&&(asc==1&&array[ix]>array[right]||asc==0&&array[ix]<array[right])){
ix=right;
}
if(ix!=index){
swapArray(array, index, ix);//交换父节点和叶子节点位置，满足最大/小堆性质
//递归向下交换，非最下层父节点与叶子节点交换会破坏下层最大/小堆性质
buildHeap(array, heapSize, ix, asc);
}
}
/**
* 交换排序：冒泡排序
* 参考: http://blog.csdn.net/morewindows/article/details/6657829
* @param array
* @param asc 0:升序  1:降序
*/
public static void bubbleSort(int[] array,int asc){
for(int i=0;i<array.length;i++){
for(int j=1;j<array.length-i;j++){
if((asc==0&&array[j-1]>array[j])||(asc==1&&array[j-1]<array[j])){
swapArray(array, j-1, j);
}
}
}
/**有点像交换排序、直接插入排序，交换次数过多
//从第二个元素开始依次与其左边元素进行比较
for(int m=1;m<array.length;m++){
//从左边最远的元素开始比较
for(int n=0;n<m;n++){
//满足条件交换位置
if((asc==0&&array[m]>array[n])
||(asc==1&&array[m]<array[n])){
swapArray(array, m, n);
}
}
}**/
display(array);
}
/**
* 交换排序：快速排序，在同为O(N*logN)的几种排序算法中效率较高，经常被使用
* 原理：从元素序列中取一个数作为基准数，左右分别放大于或小于的元素，再对左右区间重复上述操作，直到各区间只有一个数
* 参考: http://blog.csdn.net/morewindows/article/details/6684558
* @param array
* @param asc 0:升序  1:降序
*/
public static void quickSort(int[] array,int l,int r,int asc){
if(l<r){
int tmp=array[l];//把第一个节点作为基准数，视为第一个空位
int i=l;
int j=r;
//以基准数为标准，左右分别放大于或小于的节点
while(i<j){
//寻找右边小于(大于)基准数的节点位置
while(i<j&&(asc==0&&array[j]>=tmp||asc==1&&array[j]<=tmp)){
j--;
}
//把右边找到的节点放到左边的空位
array[i]=array[j];
//寻找右边大于(小于)基准数的节点位置
while(i<j&&(asc==0&&array[i]<=tmp||asc==1&&array[i]>=tmp)){
i++;
}
//把左边找到的节点放到右边的空位
array[j]=array[i];
}
//把基准数放在中间节点
array[i]=tmp;
//对中间点左边的元素重复上述操作
quickSort(array, l, i-1, asc);
//对中间点右边的元素重复上述操作
quickSort(array, i+1, r, asc);
}
display(array);
}
/**
* 归并排序：将两个(或两个以上)有序表合并成一个新的有序表
* 原理：将序列不断拆分，再反向两两合并形成有序序列
* 时间复杂度：O(nlogn)
* 参考：http://www.cnblogs.com/jingmoxukong/p/4308823.html
* @param array
* @param l 左指针
* @param r 右指针
* @param asc 0:升序  1:降序
*/
public static void mergeSort(int[] array,int l,int r,int asc){
//找出中间点，左右拆分为两个序列
int m=(l+r)/2;
if(l<r){
//左边序列，递归拆分直到间隔为0
mergeSort(array, l, m, asc);
//右边，递归拆分直到间隔为0
mergeSort(array, m+1, r, asc);
//左右归并
merge(array, l, m, r, asc);
}
display(array);
}
/**
* 左右归并为有序集合
* @param array
* @param l 左指针
* @param m 中间指针
* @param r 右指针
*/
private static void merge(int[] array,int l,int m,int r,int asc){
int[] tmp=new int[r-l+1];
int i=l;//左指针
int j=m+1;//右指针
int k=0;
//把较小的数先移到临时数组中
while(i<=m&&j<=r){
if(asc==0&&array[i]<array[j]||asc==1&&array[i]>array[j]){
tmp[k++]=array[i++];
}else{
tmp[k++]=array[j++];
}
}
//把左边剩余的数移到数组中
while(i<=m){
tmp[k++]=array[i++];
}
//把右边剩余的数移到数组中
while(j<=r){
tmp[k++]=array[j++];
}
//把临时数组中的数覆盖原数组，形成有序集合
for(k=0;k<tmp.length;k++){
array[l+k]=tmp[k];
}
}
/**
* 基数/桶排序：将序列分到有限数量的桶子里，再分别排序
* 原理：将序列分到有限数量的桶子里，再分别排序
* 时间复杂度：O(nlog(r)m)，r为所采用的基数，m为堆数
* 参考：http://www.cnblogs.com/jingmoxukong/p/4308823.html
* @param array
* @param l 左指针
* @param r 右指针
* @param asc 0:升序  1:降序
*/
public static void radixSort(int[] array,int digit,int asc){
final int radix=10;//基数，阿拉伯数字0~9，视为10个桶
int i=0;
int j=0;
int[] count=new int[radix];//存放各个桶存放数据的个数
int[] tmp=new int[array.length];
//按照从低到高位进行排序
for(int d=1;d<=digit;d++){
//置空各个桶的统计数据
for(i=0;i<radix;i++){
count[i]=0;
}
//根据位数d，统计各个桶存放数据的个数
for(i=0;i<array.length;i++){
j=array[i]/((Double)Math.pow(10, d-1)).intValue()%10;//d位上的数据
count[j]++;
}
//把count[i]的值由存放的个数改变了有边界的索引
for(i=1;i<radix;i++){
count[i]+=count[i-1];
}
//将数据依次装入临时桶里，从右向左扫描
for(i=array.length-1;i>=0;i--){
j=array[i]/((Double)Math.pow(10, d-1)).intValue()%10;//d位上的数据
tmp[count[j]-1]=array[i];//count[j]-1为第J个桶右边界的下标
count[j]--;//桶j装入数据索引减1
}
//按照桶中数据顺序放入原数据序列中
for(i=0;i<array.length;i++){
if(d==digit){
if(asc==0){
array[i]=tmp[i];
}else{
array[i]=tmp[array.length-i-1];
}
}else{
array[i]=tmp[i];
}
}
}
display(array);
}
/**
* 数组中指定位置的值交换位置
* @param array
* @param i
* @param j
*/
private static void swapArray(int[] array,int i,int j){
array[i]=array[j]^array[i];
array[j]=array[i]^array[j];
array[i]=array[i]^array[j];
}
/**
* 输出数组
* @param array
*/
private static void display(int[] array){
StringBuilder builder=new StringBuilder("[");
for(int i=0;i<array.length;i++){
builder.append(array[i]);
if(i<array.length-1){
builder.append(",");
}else{
builder.append("]");
}
}
System.out.println(builder.toString());
}
public static void main(String[] args) {
int[] array=new int[]{11,56,35,62,97,21,36,33,86,81,35};
//straightInsertSort(array, 0);
//shellSort(array, 0);
//selectSort(array, 0);
//heapSort(array, 0);
//bubbleSort(array,0);
//quickSort(array, 0, array.length-1, 0);
//mergeSort(array, 0, array.length-1,1);
radixSort(array, 3, 0);
}
}

2. 並べ替えアルゴリズムの比較表

引用

http://blog.csdn.net/hguisu/article/details/7776068

3.

並べ替えに影響を与える要因は数多くあり、平均時間計算量が低いアルゴリズムが必ずしも最適であるとは限りません。逆に、特殊な場合には、平均時間計算量が高いアルゴリズムの方が適している場合もあります。同時に、アルゴリズムを選択する際には、ソフトウェアのメンテナンスを容易にするために、その可読性も考慮する必要があります。一般的に、次の 4 つの要素を考慮する必要があります:
1) ソートするレコード数 n のサイズ
2) レコード自体のデータ量、つまりその他の情報の量。キーワードを除くレコード内。
3)、キーワードの構造と分布
4)、ソートの安定性の要件。

ソートする要素の数が n であるとします。
1) n が大きい場合、時間計算量が O(nlog2n) のソート方法 (クイック ソート、ヒープ ソート、またはマージ ソート) を使用する必要があります。
a. クイックソート: 比較に基づく内部ソートの中で、ソート対象のキーワードがランダムに分散されている場合、クイックソートの平均時間が最も短いと考えられています。許可し、安定性を要求します。
c. マージソート: ある程度の量のデータ移動があるため、挿入ソートと組み合わせて、最初に一定の長さのシーケンスを取得してからそれをマージすると、効率が向上します。
2)、nが大きい場合、メモリ空間に余裕があり、安定性が必要な場合 => マージソート
3)、nが小さい場合、直接挿入または直接選択ソートが使用できます。
a. 直接挿入ソート: 要素が順番に分散されている場合、直接挿入ソートは比較の数と移動レコードの数を大幅に削減します。
b. 要素が順番に分散されている場合。必須、直接選択ソートを選択してください
4) 従来のバブルソートは通常使用されないか、直接使用されません。
5) 基数ソート: 安定した並べ替えアルゴリズムですが、次のような制限があります:
a. キーワードは分解できます。これは数値であるため、符号なしであることが最善です。そうでないと、対応するマッピングの複雑さが増加します。最初に正の数値と負の数値を別々に並べ替えることができます。


引用

http://blog.csdn.net/hguisu/article/details/7776068