Acht Sortieralgorithmus-Praktiken

Was den Sortieralgorithmus betrifft, so wurde er in den letzten Jahren kaum verwendet. Er befindet sich grundsätzlich in einem Zustand der Nutzung und ich habe mir nie die Zeit genommen, ihn eingehend zu verstehen. Vor kurzem habe ich beschlossen, es selbst zu schreiben, um mein Verständnis zu vertiefen. Ich habe viele Informationen überprüft und viele davon wurden sehr gut analysiert, was mir geholfen hat, sie schnell zu verstehen. Vielen Dank!

1. Konzeptionelles Verständnis und Umsetzung

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. Sortieralgorithmus-Vergleichstabelle

Zitat

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

3. Auswahlkriterien für Sortieralgorithmen

Es gibt viele Faktoren, die die Sortierung beeinflussen, und Algorithmen mit geringer durchschnittlicher Zeitkomplexität sind es nicht Es muss das Beste sein. Umgekehrt kann für einige Sonderfälle manchmal ein Algorithmus mit einer hohen durchschnittlichen Zeitkomplexität besser geeignet sein. Gleichzeitig muss bei der Auswahl eines Algorithmus auch dessen Lesbarkeit berücksichtigt werden, um die Softwarewartung zu erleichtern. Im Allgemeinen müssen die folgenden vier Faktoren berücksichtigt werden:
1) die Größe der Anzahl n der zu sortierenden Datensätze
2) die Größe des Datenvolumens des Datensatzes selbst; die Größe des Datensatzes mit Ausnahme von Schlüsselwörtern. Die Menge anderer Informationen;
3), die Struktur und Verteilung von Schlüsselwörtern
4), die Anforderungen an die Sortierstabilität.

Angenommen, die Anzahl der zu sortierenden Elemente beträgt n
1) Wenn n groß ist, sollte eine Sortiermethode mit einer Zeitkomplexität von O(nlog2n) verwendet werden: schnelle Sortierung, Heap-Sortierung oder Zusammenführung Sortierreihenfolge.
a. Schnelle Sortierung: Dies gilt derzeit als die beste Methode zur internen Sortierung, wenn die zu sortierenden Schlüsselwörter zufällig verteilt sind.
b. Wenn der Speicherplatz es zulässt und Stabilität erforderlich ist; wird die Effizienz verbessern. Verbessert.
2), wenn n groß ist, ist genügend Speicherplatz vorhanden und Stabilität ist erforderlich => Zusammenführungssortierung
3), wenn n klein ist, kann direkte Einfügung oder direkte Auswahlsortierung verwendet werden.
a. Direkte Einfügungssortierung: Wenn die Elemente in der richtigen Reihenfolge verteilt werden, verringert die direkte Einfügungssortierung die Anzahl der Vergleiche und die Anzahl der verschobenen Datensätze erheblich.
b. Wenn keine Stabilität erforderlich ist, wählen Sie Direktauswahlsortierung
4). Die herkömmliche Blasensortierung wird im Allgemeinen nicht oder nicht direkt verwendet.
5) Radix-Sortierung: Es handelt sich um einen stabilen Sortieralgorithmus, der jedoch bestimmte Einschränkungen aufweist:
Die Anzahl der aufgezeichneten Schlüsselwortziffern ist gering.
c. Wenn es sich um eine Zahl handelt, ist es am besten, sie ohne Vorzeichen zu verwenden, da sonst die entsprechende Zuordnungskomplexität zunimmt. Sie können die positiven und negativen Zahlen zuerst separat sortieren.


Zitat

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