常用的排序算法

本文主要对一些基础排序算法进行温故。子曰：“温故而知新，可以为师矣。”

common-sort.png

插入排序---直接插入排序

基本思想：将一个记录插入到已经排好序的有序列表中，从而得到新的有序列表。

平均时间复杂度：O(n2)
平均空间复杂度：O(1)

1. 令i从i递增到n-1，重复(2)~(4)
2. 将元素Si保存到临时变量中
3. 确定使得条件Sj>=Si成立的最小j
4. 将子序列{Sj...Sj-1}后移一个位置到{Sj+1...Sj}
5. 将保存在临时变量中的Si复制到Sj+1

实现代码：

public void insertSort(int [] a){
    int len = a.length;
    for(int i = i;i<len-1;i++){
        int temp = a[i]; //临时存储a[i]
        int j = j-1; //小于i的索引，都认为是已经排好序的
        while(j>=0 && temp<a[j]){
            a[j+1]=a[j]; //将数据向右移动一位
            j--;
        }
        a[j+1] = temp; //找到插入的位置，将临时存储的a[i]，赋值到j+1
    }
}

插入排序---希尔排序

平均时间复杂度：O(n3/2)
平均空间复杂度：O(1)

基本思想：取一个小于n的整数d1，作为第一个增量，将数组分成d1组，在各组内进行插入排序；然后去第二个增量d2<d1，重复以上的操作，直到dt=1。

代码实现：

public void shellSort(int [] a){
    int datalen = a.length/2;
    while(datalen >0){
        for(int i=datalen;i<a.length;i++){
            int pointer = i-datalen;
            int temp = a[pointer];
            while(pointer>=0 && temp<a[pointer]){
                a[pointer+datalen]=a[pointer];
                pointer-=datalen;
            }
        a[pointer+datalen]=temp;
        }
      datalen = datalen/2;
    }
}

交换排序---冒泡排序

平均时间复杂度：O(n2)
平均空间复杂度：O(1)

基本思想：根据轻气泡不能在重气泡之下的原则，从下往上扫描，凡是违背这一原则的的轻气泡就使之向上“漂浮”，直到最后任意两个气泡都是轻者在上，重者在下为至。

1. 令i从n-1递减到1，重复步骤(2)~(4)
2. 令j从0递增到i，重复步骤(3)
3. 如果元素Sj-1和Sj成反序，交换它们
4. 结束标记，序列{S0...Si}被排序且Si最大

代码实现：

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

交换排序---快速排序

平均时间复杂度：O(nlogn)
平均空间复杂度：O(logn)

基本思想：采用了一种分治的策略，分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题，递归地解这些子问题，然后将这些子问题的解组合为原问题的解。有3个步骤：

1. 分解：将原问题分解为若干个子问题
2. 求解：递归地解决这些子问题，若子问题的规模足够小，直接求解
3. 组合：将各子问题的解组合原问题的解

代码实现：

public void quickSort(int [] a,int low,int hi){
    if(low>=hi) return;
    int j = partition(a,low,hi);
    quickSort(a,low,j-1);
    quickSort(a,j+1,hi);
}


public int partition(int [] a,int low,int hi){
    int temp = a[low];
    int i = low;
    int j = hi;
    while(i<j){
        while(i<j;temp<a[j]){
            j--;
        }
       exch(a,i,j);
        while(i<j;temp>a[i]){
            i++;
        }
        exch(a,i,j);
    }
  return j；
}


public void exch(int [] a ,int i,int j){
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

选择排序---直接选择排序

平均时间复杂度：O(n2)
平均空间复杂度：O(1)

基本思想：在第i次排序时，有序区S[1..i-1]和无序区S[i...n]，取无序区一个最小值记录R[k]，将R[k]与无序区第一个记录交换，使得S[1..i]和S[i+1..n]成为新的有序区和无序区。

代码实现：

public void selectSort(int [] a){
    for(int i = 0;i<a.length;i++){
        int minVal = Integer.MAX_VALUE;
        int minIndex = 0;
        for(int j = i;j<a.length;j++){
            int temp = a[j];
            if(temp<minVal){
                minVal = temp;
                minIndex = j;
            }
        }
        exch(a,i,minIndex);
    }

}

选择排序---堆排序

平均时间复杂度：O(nlogn)
平均空间复杂度：O(1)

基本思想：首先堆具有下列完全二叉树的性质：每个节点的值都大于或等于其左右孩子的值，称为大顶堆；或者每个节点的值都小于等于其左右孩子的值，称为小顶堆。利用这一性质，将待排序的数据构建成一个大顶堆或者小顶堆，将根结点与数据末端的元素交互，并移除数据末端元素，然后n-1继续重构一个堆，如此反复执行。

代码实现：

public void heapSort(int len){
    for(int i = len/2;i>0;i--){
        heapAjust(i,len);
    }
    for(int i = len; i>0;i--){
        exch(1,i);
        heapAjust(1,i-1);
    }
}

public void heapAjust(int s,int len){
    int temp , j;
    temp = arr[s];
    for(j=2*s;j<=len;j*=2){
        if(j<len && arr[j]<arr[j+1]){
            j++
        }
        if(temp>=arr[j])
            break;
        arr[s] = arr[j];
        s = j;
    }
    arr[s] = temp;
}

欢迎关注我的个人订阅号

个人订阅号二维码