常见排序算法总结

面试经典 Finley Fu 2020-01-16 2评论 459
常见的排序算法:冒泡排序、选择排序、插入排序、快速排序、堆排序等

   算法比较  


排序算法
时间复杂度 空间复杂度
冒泡排序 O(n2)
O(1)
选择排序 O(n2)
O(1)
插入排序 O(n2)
O(1)
快速排序 O(N*logN)
O(logn)
堆排序 O(N*logN)
O(1)

   冒泡排序  

        冒泡排序算法是把较小的元素往前调或者把较大的元素往后调。这种方法主要是通过对相邻两个元素进行大小的比较,根据比较结果和算法规则对该二元素的位置进行交换,这样逐个依次进行比较和交换,就能达到排序目的。冒泡排序的基本思想是,首先将第1个和第2个记录的关键字比较大小,如果是逆序的,就将这两个记录进行交换,再对第2个和第3个记录的关键字进行比较,依次类推,重复进行上述计算,直至完成第(n一1)个和第n个记录的关键字之间的比较,此后,再按照上述过程进行第2次、第3次排序,直至整个序列有序为止。排序过程中要特别注意的是,当相邻两个元素大小一致时,这一步操作就不需要交换位置,因此也说明冒泡排序是一种严格的稳定排序算法,它不改变序列中相同元素之间的相对位置关系。

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


   选择排序  

        选择排序算法的基本思路是为每一个位置选择当前最小的元素。选择排序的基本思想是,基于直接选择排序和堆排序这两种基本的简单排序方法。首先从第1个位置开始对全部元素进行选择,选出全部元素中最小的给该位置,再对第2个位置进行选择,在剩余元素中选择最小的给该位置即可;以此类推,重复进行“最小元素”的选择,直至完成第(n-1)个位置的元素选择,则第n个位置就只剩唯一的最大元素,此时不需再进行选择。使用这种排序时,要注意其中一个不同于冒泡法的细节。举例说明:序列58539.我们知道第一遍选择第1个元素“5”会和元素“3”交换,那么原序列中的两个相同元素“5”之间的前后相对顺序就发生了改变。因此,我们说选择排序不是稳定的排序算法,它在计算过程中会破坏稳定性。

public static void selectionSort(int[] arr){
    for (int i = 0; i < arr.length - 1; i++) {    
        int  min = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[min] > arr[j]) {
                min = j;
            }
        }
        if (min != i) {
           int tmp = arr[min];
           arr[min] = arr[i];
           arr[i] = tmp;
        }             
    }
}


   插入排序  

        插入排序算法是基于某序列已经有序排列的情况下,通过一次插入一个元素的方式按照原有排序方式增加元素。这种比较是从该有序序列的最末端开始执行,即要插入序列中的元素最先和有序序列中最大的元素比较,若其大于该最大元素,则可直接插入最大元素的后面即可,否则再向前一位比较查找直至找到应该插入的位置为止。插入排序的基本思想是,每次将1个待排序的记录按其关键字大小插入到前面已经排好序的子序列中,寻找最适当的位置,直至全部记录插入完毕。执行过程中,若遇到和插入元素相等的位置,则将要插人的元素放在该相等元素的后面,因此插入该元素后并未改变原序列的前后顺序。我们认为插入排序也是一种稳定的排序方法。插入排序分直接插入排序、折半插入排序和希尔排序3类。

private static int[] insertSort(int[]arr){
    if(arr == null || arr.length < 2){
        return arr;
    }
    for(inti=1;i<arr.length;i++){
        int temp = arr[i];
        int indx = 0;
        for(intj=i;j>0;j--){
            if(arr[j]<arr[j-1]){
                //TODO:
                arr[j] = arr[j-1];
                indx = j-1;
            }else{
                //接下来是无用功
                break;
            }
            arr[indx]=temp;
        }
    }
    return arr;
}


   快速排序  

        快速排序的基本思想是:通过一趟排序算法把所需要排序的序列的元素分割成两大块,其中,一部分的元素都要小于或等于另外一部分的序列元素,然后仍根据该种方法对划分后的这两块序列的元素分别再次实行快速排序算法,排序实现的整个过程可以是递归的来进行调用,最终能够实现将所需排序的无序序列元素变为一个有序的序列。

public static int[] qsort(int arr[],int start,int end) {
    int pivot = arr[start];
    int i = start;
    int j = end;
    while (i<j) {
        while ((i<j)&&(arr[j]>pivot)) {
            j--;
        }
        while ((i<j)&&(arr[i]<pivot)) {
            i++;
        }            
        if ((arr[i]==arr[j])&&(i<j)) {
            i++;
        } else {
            int temp = arr[i];
            arr[i] = arr[j];   
            arr[j] = temp;
        }        
    }        
    if (i-1>start) arr=qsort(arr,start,i-1);
    if (j+1<end) arr=qsort(arr,j+1,end);
    return (arr);    
}    


   堆排序  

        堆排序(英语:Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。
        在堆的数据结构中,堆中的最大值总是位于根节点(在优先队列中使用堆的话堆中的最小值位于根节点)。堆中定义以下几种操作:
        1、最大堆调整(Max Heapify):将堆的末端子节点作调整,使得子节点永远小于父节点。
        2、创建最大堆(Build Max Heap):将堆中的所有数据重新排序。
        3、堆排序(HeapSort):移除位在第一个数据的根节点,并做最大堆调整的递归运算。

/**
* 选择排序-堆排序
* @param array 待排序数组
* @return 已排序数组
*/
public static int[] heapSort(int[] array) {
    //这里元素的索引是从0开始的,所以最后一个非叶子结点array.length/2 - 1
    for (int i = array.length / 2 - 1; i >= 0; i--) {  
        adjustHeap(array, i, array.length);  //调整堆
    }

    // 上述逻辑,建堆结束
    // 下面,开始排序逻辑
    for (int j = array.length - 1; j > 0; j--) {
        // 元素交换,作用是去掉大顶堆
        // 把大顶堆的根元素,放到数组的最后;换句话说,就是每一次的堆调整之后,都会有一个元素到达自己的最终位置
        swap(array, 0, j);
        // 元素交换之后,毫无疑问,最后一个元素无需再考虑排序问题了。
        // 接下来我们需要排序的,就是已经去掉了部分元素的堆了,这也是为什么此方法放在循环里的原因
        // 而这里,实质上是自上而下,自左向右进行调整的
        adjustHeap(array, 0, j);
    }
    return array;
}

/**
* 整个堆排序最关键的地方
* @param array 待组堆
* @param i 起始结点
* @param length 堆的长度
*/
public static void adjustHeap(int[] array, int i, int length) {
    // 先把当前元素取出来,因为当前元素可能要一直移动
    int temp = array[i];
    for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {  //2*i+1为左子树i的左子树(因为i是从0开始的),2*k+1为k的左子树
        // 让k先指向子节点中最大的节点
        if (k + 1 < length && array[k] < array[k + 1]) {  //如果有右子树,并且右子树大于左子树
            k++;
        }
        //如果发现结点(左右子结点)大于根结点,则进行值的交换
        if (array[k] > temp) {
            swap(array, i, k);
            // 如果子节点更换了,那么,以子节点为根的子树会受到影响,所以,循环对子节点所在的树继续进行判断
                i  =  k;
                    } else {  //不用交换,直接终止循环
            break;
        }
    }
}

/**
* 交换元素
* @param arr
* @param a 元素的下标
* @param b 元素的下标
*/
public static void swap(int[] arr, int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}