八大排序算法总结

排序算法总结：

排序法	平均时间	最差情形	稳定度	额外空间	备注
冒泡	O(n2)	O(n2)	稳定	O(1)	n小时较好
交换	O(n2)	O(n2)	不稳定	O(1)	n小时较好
选择	O(n2)	O(n2)	不稳定	O(1)	n小时较好
插入	O(n2)	O(n2)	稳定	O(1)	大部分已排序时较好
基数	O(logRB)	O(logRB)	稳定	O(n)	B是真数(0-9)， R是基数(个十百)
Shell	O(nlogn)	O(ns) 1<s<2	不稳定	O(1)	s是所选分组
快速	O(nlogn)	O(n2)	不稳定	O(nlogn)	n大时较好
归并	O(nlogn)	O(nlogn)	稳定	O(1)	n大时较好
堆	O(nlogn)	O(nlogn)	不稳定	O(1)	n大时较好

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

插入排序

java实现：

package sort;

public class InsertSort {
    
    public static void main(String[] args) {
        
        int[] arr={70,80,31,37,10,1,48,60,33,80};
        insertSort(arr);
        
        for(int each:arr)
            System.out.print(each+" ");
    }
    
    
    public static void insertSort(int[] arr)
    {
        
        int len=arr.length;
        
        for(int i=1; i<len; i++)
        {
            for(int j=0; j<i; j++)
            {
                if(arr[i]<arr[j])
                {
                    int temp=arr[i];
                    for(int k=i; k>j; k--)
                        arr[k]=arr[k-1];
                    arr[j]=temp;
                    break;
                }
            }
        }
    }
}

c++实现

#include<iostream>
using namespace std;

void insertSort(int a[],int len);

int main()
{
    int a[]={70,80,31,37,10,1,48,60,33,80};
    int len=sizeof(a)/sizeof(int);

    insertSort(a,len);

    for(int i=0; i<len; i++)
        cout<<a[i]<<" ";
}


void insertSort(int a[],int len)
{
    int i,j;
    
    for(i=1; i<len; i++)
    {
        for(j=0; j<i; j++)
        {
            if(a[i]<a[j])
            {
                int k,temp=a[i];
                for(k=i; k>j; k--)
                    a[k]=a[k-1];
                a[k]=temp;
            }
        }
    }
}

 

 

选择排序

java实现

package sort;

public class SelectSort {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub

        int[] arr={70,80,31,37,10,1,48,60,33,80};
        
        selectSort(arr);
        
        for(int i=0; i<arr.length; i++)
            System.out.print(arr[i]+" ");
        
    }
    
    public static void selectSort(int[] arr){
        
        int i,j;
        int min,temp;
        
        for(i=0; i<arr.length; i++)
        {
            min=i;
            for(j=i; j<arr.length; j++)
            {
                if(arr[j]<arr[min])
                {
                    min=j;
                }
            }
            if(min!=i)
            {
                temp=arr[i];
                arr[i]=arr[min];
                arr[min]=temp;
            }
        }
    }
}

 

c++实现

#include<iostream>
using namespace std;

void insertSort(int a[],int len);

int main()
{
    int a[]={70,80,31,37,10,1,48,60,33,80};
    int len=sizeof(a)/sizeof(int);

    insertSort(a,len);

    for(int i=0; i<len; i++)
        cout<<a[i]<<" ";
}


void insertSort(int a[],int len)
{
    int i,j;
    
    for(i=1; i<len; i++)
    {
        for(j=0; j<i; j++)
        {
            if(a[i]<a[j])
            {
                int k,temp=a[i];
                for(k=i; k>j; k--)
                    a[k]=a[k-1];
                a[k]=temp;
            }
        }
    }
}

 

 

冒泡排序

java实现

package sort;

public class BubbleSort {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub


        int[] arr={70,80,31,37,10,1,48,60,33,80};
        
        bubbleSort(arr);
        
        for(int i=0; i<arr.length; i++)
            System.out.print(arr[i]+" ");
    }

    private static void bubbleSort(int[] arr) {
        // TODO Auto-generated method stub
        
        int i,j;
        int temp;
        
        for(i=arr.length-1; i>0; i--)
        {
            for(j=0; j<i; j++)
            {
                if(arr[j]>arr[j+1])
                {
                    temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
        }
    }

}

c++实现

#include<iostream>
using namespace std;

void bubbleSort(int a[],int len);

int main()
{
    int a[]={70,80,31,37,10,1,48,60,33,80};
    int len=sizeof(a)/sizeof(int);

    bubbleSort(a,len);

    for(int i=0; i<len; i++)
        cout<<a[i]<<" ";
}

void bubbleSort(int a[],int len)
{
    int i,j;
    int temp;
    for(i=len-1; i>0; i--)
    {
        for(j=0; j<i; j++)
        {
            if(a[j]>a[j+1])
            {
                temp=a[j+1];
                a[j+1]=a[j];
                a[j]=temp;
            }
        }
    }
}

 

 

交换排序

java实现

package sort;

public class SwapSort {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub

        int[] arr={70,80,31,37,10,1,48,60,33,80};
        
        swaptSort(arr);
        
        for(int i=0; i<arr.length; i++)
            System.out.print(arr[i]+" ");
    }

    private static void swaptSort(int[] arr) {
        // TODO Auto-generated method stub
        
        int i,j;
        int temp;
        
        for(i=1; i<arr.length; i++)
        {
            for(j=0; j<i; j++)
            {
                if(arr[i]<arr[j])
                {
                    temp=arr[i];
                    arr[i]=arr[j];
                    arr[j]=temp;
                }
            }
        }
    }

}

 

 

 

快速排序

java实现

package sort;

public class QuickSort {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        int []a={16,7,3,20,17,8};
        
        for(int i=0; i<a.length; i++)
            System.out.print(a[i]+" ");
        
        quickSort(a);
        System.out.println();
        
        for(int i=0; i<a.length; i++)
            System.out.print(a[i]+" ");
    }
    
    public static void quickSort(int a[])
    {
        quickSort(a,0,a.length-1);
    }
    
    public static void quickSort(int a[],int l,int r){
        int i=l,j=r;
        int x=a[i];
        
        while(i<j)
        {
            while(i<j && x<=a[j])
                j--;
            if(i<j)
                a[i]=a[j];
            
            while(i<j && x>a[i])
                i++;
            if(i<j)
                a[j]=a[i];
        }
        
        if(l<i-1)
            quickSort(a,l,i-1);
        if(i+1<r)
            quickSort(a,i+1,r);
        
        a[i]=x;
    }

}

c++实现

#include<iostream>
using namespace std;

void quickSort(int a[],int len);
void quickSort(int a[],int l,int r);

int main()
{
    int a[]={70,80,31,37,10,1,48,60,33,80};
    int len=sizeof(a)/sizeof(int);

    quickSort(a,len);

    for(int i=0; i<len; i++)
        cout<<a[i]<<" ";
}

void quickSort(int a[],int len)
{
    quickSort(a,0,len-1);
}

void quickSort(int a[],int l,int r)
{
    int i=l,j=r;
    int x=a[i];

    while(i<j)
    {
        while(i<j && x<=a[j])
            j--;
        if(i<j)
            a[i]=a[j];

        while(i<j && x>a[i])
            i++;
        if(i<j)
            a[j]=a[i];
    }

    if(l<i-1)
        quickSort(a,l,i-1);
    if(i+1<r)
        quickSort(a,i+1,r);

    a[i]=x;
}

 

 

希尔排序

java实现

package sort;

public class ShellSort {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub

        int[] arr={70,80,31,37,10,1,48,60,33,80};
        
        shellSort(arr);
        
        for(int i=0; i<arr.length; i++)
            System.out.print(arr[i]+" ");
    }

    private static void shellSort(int[] arr) {
        // TODO Auto-generated method stub
        
        int i,j,k;
        int gap,temp;
        
        for(gap=arr.length/2; gap>0; gap=gap/2)
        {
            for(i=0; i<gap; i++)
            {
                for(j=i+gap; j<arr.length; j=j+gap)
                {
                    if(arr[j]<arr[j-gap])
                    {
                        temp=arr[j];
                        arr[j]=arr[j-gap];
                        arr[j-gap]=temp;
                    }
                }
            }
        }
    }

}

 

 

 

归并排序

java实现

package sort;

public class MergeSort {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        int[] arr={16,7,3,20,17,8};
        
        int[] result=mergeSort(arr);
        
        for(int i=0; i<result.length; i++)
            System.out.print(result[i]+" ");
    }

    private static int[] mergeSort(int[] arr) {
        // TODO Auto-generated method stub
        
        if(arr.length==1)
            return arr;
        
        int half=arr.length/2;
        int[] a=new int[half];
        int[] b=new int[arr.length-half];
        
        System.arraycopy(arr, 0, a, 0, half);
        System.arraycopy(arr, half, b, 0, b.length);
        a=mergeSort(a);
        b=mergeSort(b);
        
        return mergeSortSub(a,b);
    }
    
    private static int[] mergeSortSub(int[] a,int[] b){
        
        int[] result=new int[a.length+b.length];
        int i=0,j=0,k=0;
        
        while(i<a.length && j<b.length)
        {
            if(a[i]<b[j])
                result[k++]=a[i++];
            else
                result[k++]=b[j++];
        }
        while(i<a.length)
            result[k++]=a[i++];
        while(j<b.length)
            result[k++]=b[j++];
        
        return result;
    }
}

 

堆排序

package 经典;

public class CheapSort {
    
    public static final int MAX=10;
    
    public static void main(String[] args){
        int []a={16,7,3,20,17,8};
        int len=a.length;
            
        buildHeap(a,len);
        
        for(int i=0; i<len; i++)
            System.out.print(a[i]+",");
        
        sort(a,len);
        System.out.println();
        
        for(int i=0; i<len; i++)
            System.out.print(a[i]+",");
        
    }
    
    public static void sort(int[] a,int size){
        
        int n=size-1;
        
        if(n==0)
            return;
        swap(a,0,n);
        
        adjustHeap(a,0,n);
        
        sort(a,n);
    }
    
    public static void swap(int[] a,int i,int j){
        int temp;
        temp=a[i];
        a[i]=a[j];
        a[j]=temp;
    }
    
    public static void buildHeap(int[] a,int size){
        
        for(int i=(size-1)/2; i>=0; i--)
            adjustHeap(a,i,size);
    }

    private static void adjustHeap(int[] a, int i, int size) {
        // TODO Auto-generated method stub
    
        int lchild=i*2+1;
        int rchild=i*2+2;
        int max=i;
        
        if(lchild<size && a[lchild]>a[max])
            max=lchild;
        if(rchild<size && a[rchild]>a[max])
            max=rchild;
        if(max!=i)
        {
            swap(a,i,max);
            adjustHeap(a,max,size);
        }

    }
}