排序算法

前言

  • 现在排序算法经过长时间的演变,发展处各种不同的排序算法。不得不说在日常开发以及日后的研究生活中还是比较常见以及使用的。再此对各种排序算法做一个记录,方便日后比较和查阅。

    20161209148121497698544.jpg
    20161209148121497698544.jpg

  • 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。

    20161209148125804785959.jpg
    20161209148125804785959.jpg

  • 当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序、堆排序或归并排序序。

  • 快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;

直接插入排序(插入排序)

  • 介绍
    它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。
  • 步骤
    1. 从第一个元素开始,该元素可以认为已经被排序
    2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
    3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
    4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
    5. 将新元素插入到该位置中
    6. 重复步骤2
  • 最优复杂度:当输入数组就是排好序的时候,复杂度为O(n),而快速排序在这种情况下会产生O(n2)的复杂度。
  • 最差复杂度:当输入数组为倒序时,复杂度为O(n2)
  • 比较适合用于“少量元素的数组”。

  • 代码

    import java.util.*;
    

class Untitled {
public static void main(String[] args) {
Random ran = new Random();
int[] sort = new int[10];
for (int i = 0;i < 10;i++) {
sort[i] = ran.nextInt(50);
}
System.out.println("排序前的数组为");
for (int i : sort) {
System.out.print(i + " ");
}
System.out.println();
directInsertSort(sort);
System.out.println("排序后的数组为");
for (int i : sort) {
System.out.print(i + " ");
}
}
/**
* 直接插入排序
*

* @param sort
*/
private static void directInsertSort(int[] sort) {

for (int i = 1; i < sort.length; i++) {

int index = i - 1;

int temp = sort[i];

while (index >= 0 && sort[index] > temp) {

sort[index + 1] = sort[index];

index--;

}

sort[index + 1] = temp;

}

}
}


- **示例**  

![2016120914812599573549.jpg](http://ohtrrgyyd.bkt.clouddn.com/2016120914812599573549.jpg?imageView2/0/format/jpg)
## 希尔排序

- **介绍**  
希尔排序,也称递减增量排序算法,是插入排序的一种高速而稳定的改进版本。  
希尔排序是基于插入排序的以下两点性质而提出改进方法的:
    1. 插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率
    2. 但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位

- **步骤**  
    1. 选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;
    2. 按增量序列个数k,对序列进行k 趟排序;
    3. 每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。
- **示例**  

![2016120914812602403259.jpg](http://ohtrrgyyd.bkt.clouddn.com/2016120914812602403259.jpg?imageView2/0/format/jpg)

- **排序效果**

    ![2016120965074shell.gif](http://ohtrrgyyd.bkt.clouddn.com/2016120965074shell.gif)
    
## 冒泡排序

- **介绍**  
冒泡排序(Bubble Sort,台湾译为:泡沫排序或气泡排序)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

- **步骤**  
    1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
    2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
    3. 针对所有的元素重复以上的步骤,除了最后一个。
    4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

- **代码**
``` java
import java.util.*;
class test1 {
    public static void main(String[] args) {
        Random ran = new Random();
        int[] sort = new int[10];
        for (int i = 0;i < 10;i++) {
            sort[i] = ran.nextInt(50);
        }
        System.out.println("排序前的数组为");
        for (int i : sort) {
            System.out.print(i + " ");
        }
        System.out.println();
        buddleSort(sort);
        System.out.println("排序后的数组为");
        for (int i : sort) {
            System.out.print(i + " ");
        }
    }
    
    public static void buddleSort(int[] sort){
        for (int i = 1;i < sort.length;i++) {
            for (int j = 0;j < sort.length - i;j++) {
                if (sort[j] > sort[j+1]) {
                    int temp = sort[j];
                    sort[j] = sort[j + 1];
                    sort[j + 1] = temp;
                }
            }
        }
    }
}
  • 示例

20161209148126075351022.jpg
20161209148126075351022.jpg

  • 排序效果
    2016120956722maopao2.gif
    2016120956722maopao2.gif
    2016120989640maopao.gif
    2016120989640maopao.gif

选择排序

  • 介绍

    选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾。以此类推,直到所有元素均排序完毕。

  • 步骤

    1. 从n个记录中找出关键码最小的记录与第一个记录交换;
    2. 从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换;
    3. 以此类推.....
    4. 第i 趟,则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换;
    5. 直到整个序列按关键码有序。
  • 代码

    import java.util.*;
    

class Untitled {
public static void main(String[] args) {
Random ran = new Random();
int[] sort = new int[10];
for (int i = 0;i < 10;i++) {
sort[i] = ran.nextInt(50);
}
System.out.println("排序前的数组为");
for (int i : sort) {
System.out.print(i + " ");
}
System.out.println();
selectSort(sort);
System.out.println("排序后的数组为");
for (int i : sort) {
System.out.print(i + " ");
}
}

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

}

- **示例**  

    ![20161209148125990659042.jpg](http://ohtrrgyyd.bkt.clouddn.com/20161209148125990659042.jpg?imageView2/0/format/jpg)
- **排序效果**  

    ![2016120919414selection.gif](http://ohtrrgyyd.bkt.clouddn.com/2016120919414selection.gif)
    
## 快速排序

- **介绍**  
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来,且在大部分真实世界的数据,可以决定设计的选择,减少所需时间的二次方项之可能性。

- **步骤**  
    1. 从数列中挑出一个元素,称为 “基准”(pivot)
    2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
    3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
- **代码**
``` java
import java.util.*;

class Untitled {
    public static void main(String[] args) {
        Random ran = new Random();
        int[] sort = new int[10];
        for (int i = 0;i < 10;i++) {
            sort[i] = ran.nextInt(50);
        }
        System.out.println("排序前的数组为");
        for (int i : sort) {
            System.out.print(i + " ");
        }
        System.out.println();
        quickSort(sort, 0, sort.length - 1);
        System.out.println("排序后的数组为");
        for (int i : sort) {
            System.out.print(i + " ");
        }
    }
    
    public static void quickSort(int[] sort, int start, int end) {  
            // 设置关键数据key为要排序数组的第一个元素,  
            // 即第一趟排序后,key右边的数全部比key大,key左边的数全部比key小  
            int key = sort[start];  
            // 设置数组左边的索引,往右移动判断比key大的数  
            int i = start;  
            // 设置数组右边的索引,往左移动判断比key小的数  
            int j = end;  
            // 如果左边索引比右边索引小,则还有数据没有排序  
            while (i < j) {  
                while (sort[j] > key && j > start) {
                    j--;
                }
                while (sort[i] < key && i < end) {
                    i++;
                }
                if (i < j) {
                    int temp = sort[i];
                    sort[i] = sort[j];
                    sort[j] = temp;
                }
            }
            // 如果左边索引比右边索引要大,说明第一次排序完成,将sort[j]与key对换
            // 即保持了key左边的数比key小,key右边的数比key大
            if (i > j) {
                int temp = sort[j];
                sort[j] = sort[start];
                sort[start] = temp;
            }
            //递归调用
            if (j > start && j < end) {
                quickSort(sort, start, j - 1);
                quickSort(sort, j + 1, end);
            }
        }
}
  • 示例

    • 一趟排序的过程
      jpg
      jpg
    • 排序的全过程
      20161209148126085747.jpg
      20161209148126085747.jpg
  • 排序效果

    2016120919907quick.gif
    2016120919907quick.gif

归并排序

  • 介绍

    归并排序(Merge sort,台湾译作:合并排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用

  • 步骤

    1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
    2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置
    3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
    4. 重复步骤3直到某一指针达到序列尾
    5. 将另一序列剩下的所有元素直接复制到合并序列尾
  • 示例

20161209148126088883248.jpg
20161209148126088883248.jpg

  • 排序效果

    2016120958071guibing.gif
    2016120958071guibing.gif

堆排序

  • 介绍

    堆积排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆性质:即子结点的键值或索引总是小于(或者大于)它的父节点。由堆的定义可以看出,堆顶元素(即第一个元素)必为最小项(小顶堆)。若以一维数组存储一个堆,则堆对应一棵完全二叉树,且所有非叶结点的值均不大于(或不小于)其子女的值,根结点(堆顶元素)的值是最小(或最大)的。

    1. 大顶堆序列:(96, 83,27,38,11,09)
    2. 小顶堆序列:(12,36,24,85,47,30,53,91)
      jpg
      jpg

      初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树(一维数组存储二叉树),调整它们的存储序,使之成为一个堆,将堆顶元素输出,得到n 个元素中最小(或最大)的元素,这时堆的根节点的数最小(或者最大)。然后对前面(n-1)个元素重新调整使之成为堆,输出堆顶元素,得到n 个元素中次小(或次大)的元素。依此类推,直到只有两个节点的堆,并对它们作交换,最后得到有n个节点的有序序列。称这个过程为堆排序。
  • 步骤

    • 调整小顶堆的方法
      1. 设有m 个元素的堆,输出堆顶元素后,剩下m-1 个元素。将堆底元素送入堆顶(最后一个元素与堆顶进行交换),堆被破坏,其原因仅是根结点不满足堆的性质。
      2. 将根结点与左、右子树中较小元素的进行交换。
      3. 若与左子树交换:如果左子树堆被破坏,即左子树的根结点不满足堆的性质,则重复方法(2).
      4. 若与右子树交换,如果右子树堆被破坏,即右子树的根结点不满足堆的性质。则重复方法(2).
      5. 继续对不满足堆性质的子树进行上述交换操作,直到叶子结点,堆被建成。
        2016120914812606079728.jpg
        2016120914812606079728.jpg
    • n个元素初始建堆的过程(建堆方法:对初始序列建堆的过程,就是一个反复进行筛选的过程。)
      1. n 个结点的完全二叉树,则最后一个结点是第
        20161209148126069681443.jpg
        20161209148126069681443.jpg
        个结点的子树。
      2. 筛选从第
        jpg
        jpg
        个结点为根的子树开始,该子树成为堆。
      3. 之后向前依次对各结点为根的子树进行筛选,使之成为堆,直到根结点。
      4. 如图建堆初始过程:无序序列:(49,38,65,97,76,13,27,49)
        2016120914812607398530.jpg
        2016120914812607398530.jpg
  • 排序效果

    2016120979146heapsort.gif
    2016120979146heapsort.gif

2015/7/22 posted in  算法