今天,准备填完昨天没填的坑,将排序算法方面的知识系统的学习一下,但是在简单的了解了一下后,有些不知如何组织学习了,因为排序算法的种类,实在是太多了,各有优略,各有适用的场景.有些不知所措,从何开始.
最后按照常规思路,我将逐次从排序算法的了解,常用的几种排序算法的原理及实现,几种算法的对比以及适用场景.三个方面展开对排序算法的学习.
- 排序算法的基本了解
在我们学习一样知识,技术之前,首先我们应当对它有一个基本的了解,然后在了解的基础上逐渐深入学习.
在计算机科学与数学中，排序算法（Sorting algorithm）是一种能将一串数据依照特定排序方式进行排列的一种算法。最常用到的排序方式是数值顺序以及字典顺序。有效的排序算法在一些算法例如搜索算法与合并算法中是重要的.基本上，排序算法的输出必须遵守下列两个原则：
- 输出结果为递增序列（递增是针对所需的排序顺序而言）
- 输出结果是原输入的一种排列、或是重组
而在计算机科学种关于排序算法的分类,也十分有趣,是直接按照排序算法的性能分类的,而排序算法的性能又是以时间复杂度,空间复杂度来判断的,而在排序算法中,主要被考虑到的当然就是时间复杂度了,毕竟一组数据的排序快慢是可以很直观的影响到其性能的.
- 时间复杂度与空间复杂度
时间复杂度,就是一个定性描述算法执行时间的函数.空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度.
由于时间复杂度的定义比较难以使人理解,我将另写一篇文章,全面总结和学习一下时间复杂度和空间复杂度的相关知识,这里就不大篇幅的来进行说明了.
几种常用的排序算法的探讨
排序算法是真的有很多,
经过选择,在这里选取其中最常使用到的6种排序算法进行探讨,关于一些较特殊的,高级的算法在之后需要使用到的时候再去学习.
- 最基本的冒泡,选择,插入排序
- 进阶级别的希尔,归并,快速排序
-
算法的实现原理
- 冒泡排序
冒泡排序,作为最简单的最基础的排序方法,被广为人知,其是在排序算法问题之初就自然而然使人想到并运用到的排序算法,可以称之为排序算法的基础.
其算法思路是通过循环不断对比相邻的两个数据,使小的向前,大的向后,两者交换,较小的数像气泡一样不断上浮,最终完成排序,因此形象的称之为冒泡排序.
/**
* 冒泡排序
* 通过两个for循环来排序数组
* 外层循环控制需要循环的轮次
* 内层循环控制相邻元素的对比及交换.
*/
public void BubbleSort(int[] arr){
long startime = System.nanoTime(); // 记录程序开始运行的时间点
for (int i=1;i<arr.length;i++){ // 外层for循环
for (int j=0;j<arr.length-i;j++){ //内层for循环,arr.length-i表示每进行完一轮就将循环对比的的次数减小一次,因为最后面的顺序都是每次循环中最大的,顺序已经排好,不需要再进行对比了.
if (arr[j]>arr[j+1]){ //判断交换的条件,如果当前元素比后一个元素大就交换两者位置
int a=arr[j+1]; // 两个数的交换代码
arr[j+1]=arr[j];
arr[j]=a;
}
}
}
System.out.println(Arrays.toString(arr));
long endtime = System.nanoTime(); // 记录程序结束的时间点
System.out.println("运行时间:"+(endtime-startime)+"ns"); // 输出程序运行的时间(开始结束的时间差)
}
- 选择排序
选择排序算法思想是在末未排序的序列中找到最小的一个元素,然后和当前的首位元素交换位置,之后在循环在未排序的序列中找到最小的元素,将其插入到已排序的末尾位置.
/**
* 选择排序
* 选择排序也是通过两个for循环来实现的
* 外层for循环控制循环轮次,总共n-1轮
* 此外我们还需要声明一个局部变量记录每次循环对比的最小元素的下标.
* 内存for循环,通过依次对比比较,将当前未排序的序列中最小元素的下标记录下来.
*最后通过if判断找到的下标与最开始的下标i是否相同,不相同就交换两者对应的元素
*/
public void Selectsort(int[] arr){
System.out.println("选择排序:");
long startime = System.nanoTime();
for(int i=0;i<arr.length-1;i++){ // 控制循环的轮次,总共需要n-1次.
int min =i; // 声明成员变量,用来储存最小元素的下标.
for(int j=i+1;j<arr.length;j++){ // 内层for循环,j=i+1是为了将序列分开为i表示的已排列,和i+1及之后的未排列两部分,
if(arr[j]<arr[min]){ // 判断条件,在未排列(即i+1之后的序列.)序列里找到最小元素
min =j; // 将最小元素的下标保存到成员变量min中
}
}
if(min !=i){ // 判断条件,判断最小元素是否和当前首位元素相同,
// 交换位置.
int a=arr[i];
arr[i]=arr[min];
arr[min]=a;
}
}
System.out.println(Arrays.toString(arr)); // Arrays类的toAString方法,遍历输出数组
long endtime=System.nanoTime();
System.out.println("运行时间:"+(endtime-startime)+"ns");
}
- 插入排序
插入排序的算法思路也是将序列分为已排序和未排序两部分,然后从未排序的首位开始,依次和已排序的每个元素对比,大于或等于就插在该元素后一位,小于就插入到该元素前一位.插入排序是最容易理解的排序方法,其就像我们打扑克是的插牌一样.
/**
* 插入排序
*插入排序也是通过嵌套循环实现排序的.
* y原始案例通过for,while循环嵌套实现,
*/
public void Insertsort(int[] arr){
long startime=System.nanoTime();
System.out.println("插入排序:");
int[] copyarr=Arrays.copyOf(arr,23); // 复制数组,以防改变了数组arr.
for (int i=1;i<copyarr.length;i++){ //外层循环控制轮次.
int tmp=copyarr[i]; //将当前未排序的序列首位元素抽出.
int j=i-1; // 定义局部变量 j代表i前面的已排序序列的末位
while(j>=0 && copyarr[j]>tmp){ // while循环控制,从已排序末位逐渐往前对比,如果比tmp大.
copyarr[j+1]=copyarr[j]; //就交换两者值,
j--; // j自减一,实现循环比较交换,排序
}
copyarr[j+1]=tmp; // 其他条件下,说明tmp就是当前的最小值,直接将tmp赋值给copyarr[j+1].
}
System.out.println(Arrays.toString(copyarr));
long endtime=System.nanoTime();
System.out.println("运行时间:"+(endtime-startime)+"ns");
}
冒泡排序,选择排序,插入排序,都是最早,最简单演变下的排序算法,其时间复杂度相同,是最慢的排序算法,其在循环上进行了太多的重复性,无意义的循环操作.
- 希尔排序
希尔排序也是一种递增减量算法,是插入排序的更高效的版本.希尔排序主要根据插入排序的两点改进的:- 当插入排序在处理趋近于正序的的序列时,效率最高,可以趋近于线性排序的效率.
- 插入排序每次只对一个数据进行操作移动,无疑使其效率低化.
希尔排序的基本思路:先将待排序列分为若干个子序列,再分别使用插入排列.在基本有序之后,再全部序列进行插入排列.也就是分组插入排列加插入排列.
/**
* 希尔排列
* 希尔排列是插入排列的进阶版
* 相当于将无序序列分成为多个子级无序序列,再分别进行插入排列.
*/
public void Shellsort(int[] arr) {
long startime = System.nanoTime();
System.out.println("希尔排序:");
int[] copyarr = Arrays.copyOf(arr, 23);
for (int gap = copyarr.length / 2; gap > 0; gap /= 2) { // for循环控制分组情况,每次循环将序列拆分为两组直到不能拆分为止.
for (int j = gap; j < copyarr.length; j++) { //然后通过for循环控制每组无序序列直接进行插入排序
int temp = copyarr[j];
int k;
for (k = j - gap; k >= 0 && copyarr[k] > temp; k -= gap) {
copyarr[k + gap] = copyarr[k];
}
copyarr[k + gap] = temp;
}
}
System.out.println(Arrays.toString(copyarr));
long endtime = System.nanoTime();
System.out.println("运行时间:" + (endtime - startime) + "ns");
}
- 归并排序
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一个十分高效的排序方法,并且其在任何情况下,时间复杂度都是相同的,但高效的同时,必然会牺牲一定的内存空间,由于归并排序需要一块额外的内存储存数组,所以可以说占用额外的内存空间是它唯一的缺点,这一点也注定了,它将不适合大型,大规模数据的排序.
其实现思路是,通过递归,或迭代的方式,将序列分成两个有序的序列,然后比较合并两个有序序列.合并两个有序序列是十分高效的.可以取景于O(n).
归并排序的原理图解:
分,即通过递归不断分组,治,将排序好的分组合并.
/**
* 归并排序
* 这里通过两个方法的调用实现.
* mergesort方法,主要将数组copy并分为左右两个序列.
* 通过调用本身实现不断的分化.
*/
public int[] Mergesort(int[] arr){
int[] copyarr = Arrays.copyOf(arr, arr.length);
if (copyarr.length<2){
return copyarr;
}
int middle =(int)Math.floor(copyarr.length / 2); // 将序列的长度一分为二.
int[] left = Arrays.copyOfRange(copyarr, 0, middle);
int[] right = Arrays.copyOfRange(copyarr, middle, copyarr.length);
// 返回值调用合并方法,将排序后的分组不断合并.最后返回一个完整的排序后的序列.
return merge(Mergesort(left),Mergesort(right));
}
protected int[] merge(int[] left, int[] right) { //传参,将左右两个无序序列传进来.
int[] result = new int[left.length + right.length]; //定义一个新的空数组,长度为左右序列的长度之和,
int i = 0; // 声明一个成员变量i.
while (left.length > 0 && right.length > 0) { // while 循环控制条件
if (left[0] <= right[0]) { // if判断语句,判断左右序列对应位置元素的大小.
result[i++] = left[0]; // 然后将小的元素存放在合并数组的对应位置中.
left = Arrays.copyOfRange(left, 1, left.length);
} else {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
}
while(left.length>0){ // 不满足以上while条件跳出循环时,执行,
result[i++] = left[0];
left = Arrays.copyOfRange(left,1,left.length);
}
while(right.length>0){
result[i++] = right[0];
right = Arrays.copyOfRange(right,1,right.length);
}
return result; // 返回排序合并后的序列.
}
- 快速排序
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
快速排序也是在分治思想上的又一经典的应用,在大部分情况下,快速排序总是最高效的,比归并排序还要高效的多,且其适用于大多所情况下,在无序的随机数排序上表现也要好的多,但同时它的缺点也很明显,它的时间按复杂并不固定,存在最坏情况,时间复杂度波动非常大,且其实现思路也是基于递归思想的,其空间复杂度会很高,占用额外的内存.
本质上,快速排序是在冒泡排序的基础上演变而来的分而治之的思想,其思路是:从序列中挑选一个基准值,将大于该数的数放在该基准的右边,小的放在左边,然后使用递归,依次将两边的序列排序.
/**
* 快速排序
*快速排序是分而治之的经典应用之一
* 通过递归调用的方式实现排序,
* 在大多情况下,其效率是最高的.
*/
public int[] sort(int[] arr){ // sort 方法 用来出copy数组,并调用排序方法.
int[] copyarr=Arrays.copyOf(arr,arr.length);
return quicksort(copyarr,0,copyarr.length-1);
}
// 快速排序方法.
private int[] quicksort(int[] arr,int left,int right){ //传入参数,待排序的数组,左下标,及数组长度减1.
if(left<right){ // if判断条件,这里没有else是因为left必然是小于right的.如果等于的话,直接返回数组就可以了.
int partitionindex = partition(arr,left,right); // 声明局部变量,调用分区方法,递归调用.
quicksort(arr,left,partitionindex-1); //
quicksort(arr,partitionindex+1,right); // 递归调用本身,
}
return arr;
}
/**
* 分区方法,将无序序列以基准为界分别放在左右两边,
* 真正的比较交换操作,是在这个分区方法里实现的.
* 然后在通过前面的递归调用,来循环使用分区方法,实现排序.
*/
private int partition(int[] arr,int left,int right){
int pivot =left;
int index = pivot+1;
for (int i=index;i<=right;i++){
if (arr[i]<arr[pivot]){
swap(arr,i,index);
index++;
}
}
swap(arr,pivot,index-1);
return index-1;
}
// 封装通用方法,将数组arr中的arr[i]与arr[j]的值交换
private void swap(int[] arr,int i,int j){
int temp = arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
- 源代码
package day_4_6;
import java.util.Arrays;
/**
* @outhor xiaoshe
* @date 2019/4/6 - @time 11:20
* 排序算法
*/
public class Sty_Sortalgrithm {
public static void main(String[] args) {
int[] arr = {5, 2, 4, 1, 3, 7, 9, 5, 6, 8, 0, 9, 10, 13, 11, 15, 12, 17, 14, 13, 18, 19, 20};
Sty_Sortalgrithm sortalgrithm = new Sty_Sortalgrithm();
sortalgrithm.BubbleSort(arr);
sortalgrithm.Selectsort(arr);
sortalgrithm.Insertsort(arr);
sortalgrithm.Shellsort(arr);
System.out.println("归并排序:");
System.out.println(Arrays.toString(sortalgrithm.Mergesort(arr)));
System.out.println("快速排序:");
System.out.println(Arrays.toString(sortalgrithm.sort(arr)));
}
/**
* 冒泡排序
* 通过两个for循环来排序数组
* 外层循环控制需要循环的轮次
* 内层循环控制相邻元素的对比及交换.
*/
public void BubbleSort(int[] arr) {
long startime = System.nanoTime(); // 记录程序开始运行的时间点
int[] copyarr = Arrays.copyOf(arr, 23);
System.out.println("冒泡排序:");
for (int i = 1; i < copyarr.length; i++) { // 外层for循环
for (int j = 0; j < copyarr.length - i; j++) { //内层for循环,arr.length-i表示每进行完一轮就将循环对比的的次数减小一次,因为最后面的顺序都是每次循环中最大的,顺序已经排好,不需要再进行对比了.
if (copyarr[j] > copyarr[j + 1]) { //判断交换的条件,如果当前元素比后一个元素大就交换两者位置
int a = copyarr[j + 1]; // 两个数的交换代码
copyarr[j + 1] = copyarr[j];
copyarr[j] = a;
}
}
}
System.out.println(Arrays.toString(copyarr)); // Arrays类中的toString方法遍历输出数组.
long endtime = System.nanoTime(); // 记录程序结束的时间点
System.out.println("运行时间:" + (endtime - startime) + "ns"); // 输出程序运行的时间(开始结束的时间差)
}
/**
* 选择排序
* 选择排序也是通过两个for循环来实现的
* 外层for循环控制循环轮次,总共n-1轮
* 此外我们还需要声明一个局部变量记录每次循环对比的最小元素的下标.
* 内存for循环,通过依次对比比较,将当前未排序的序列中最小元素的下标记录下来.
* 最后通过if判断找到的下标与最开始的下标i是否相同,不相同就交换两者对应的元素
*/
public void Selectsort(int[] arr) {
long startime = System.nanoTime();
int[] copyarr = Arrays.copyOf(arr, 23);
System.out.println("选择排序:");
for (int i = 0; i < copyarr.length - 1; i++) { // 控制循环的轮次,总共需要n-1次.
int min = i; // 声明成员变量,用来储存最小元素的下标.
for (int j = i + 1; j < copyarr.length; j++) { // 内层for循环,j=i+1是为了将序列分开为i表示的已排列,和i+1及之后的未排列两部分,
if (copyarr[j] < copyarr[min]) { // 判断条件,在未排列(即i+1之后的序列.)序列里找到最小元素
min = j; // 将最小元素的下标保存到成员变量min中
}
}
if (min != i) { // 判断条件,判断最小元素是否和当前首位元素相同,
// 交换位置.
int a = copyarr[i];
copyarr[i] = copyarr[min];
copyarr[min] = a;
}
}
System.out.println(Arrays.toString(copyarr)); // Arrays类的toAString方法,遍历输出数组
long endtime = System.nanoTime();
System.out.println("运行时间:" + (endtime - startime) + "ns");
}
/**
* 插入排序
* 插入排序也是通过嵌套循环实现排序的.
* y原始案例通过for,while循环嵌套实现,
*/
public void Insertsort(int[] arr) {
long startime = System.nanoTime();
System.out.println("插入排序:");
int[] copyarr = Arrays.copyOf(arr, 23); // 复制数组,以防改变了数组arr.
for (int i = 1; i < copyarr.length; i++) { //外层循环控制轮次.
int temp = arr[i]; // 声明temp,将此时未排序的首位元素抽出.
int j;
for (j = i - 1; j >= 0 && copyarr[j] > temp; j--) { // 内存for循环和判断条件合并.
//当无序序列首位元素(temp)小于有序序列末尾元素(copyarr[j])时
//就将j的值赋给j+1,这里的j+1=i;之所以使用j+1是为了能够在条件不满足时在内层for循环中循环进行判断.
copyarr[j + 1] = copyarr[j];
}
copyarr[j + 1] = temp; //在外层循环其他条件下,直接将temp赋值给j+1
}
System.out.println(Arrays.toString(copyarr));
long endtime = System.nanoTime();
System.out.println("运行时间:" + (endtime - startime) + "ns");
}
/**
* 希尔排序
* 希尔排列是插入排列的进阶版
* 相当于将无序序列分成为多个子级无序序列,再分别进行插入排列.
*/
public void Shellsort(int[] arr) {
long startime = System.nanoTime();
System.out.println("希尔排序:");
int[] copyarr = Arrays.copyOf(arr, 23);
for (int gap = copyarr.length / 2; gap > 0; gap /= 2) { // for循环控制分组情况,每次循环将序列拆分为两组直到不能拆分为止.
for (int j = gap; j < copyarr.length; j++) { //然后通过for循环控制每组无序序列直接进行插入排序
int temp = copyarr[j];
int k;
for (k = j - gap; k >= 0 && copyarr[k] > temp; k -= gap) {
copyarr[k + gap] = copyarr[k];
}
copyarr[k + gap] = temp;
}
}
System.out.println(Arrays.toString(copyarr));
long endtime = System.nanoTime();
System.out.println("运行时间:" + (endtime - startime) + "ns");
}
/**
* 归并排序
* 这里通过两个方法的调用实现.
* mergesort方法,主要将数组copy并分为左右两个序列.
* 通过调用本身实现不断的分化.
*/
public int[] Mergesort(int[] arr){
int[] copyarr = Arrays.copyOf(arr, arr.length);
if (copyarr.length<2){
return copyarr;
}
int middle =(int)Math.floor(copyarr.length / 2); // 将序列的长度一分为二.
int[] left = Arrays.copyOfRange(copyarr, 0, middle);
int[] right = Arrays.copyOfRange(copyarr, middle, copyarr.length);
// 返回值调用合并方法,将排序后的分组不断合并.最后返回一个完整的排序后的序列.
return merge(Mergesort(left),Mergesort(right));
}
protected int[] merge(int[] left, int[] right) { //传参,将左右两个无序序列传进来.
int[] result = new int[left.length + right.length]; //定义一个新的空数组,长度为左右序列的长度之和,
int i = 0; // 声明一个成员变量i.
while (left.length > 0 && right.length > 0) { // while 循环控制条件
if (left[0] <= right[0]) { // if判断语句,判断左右序列对应位置元素的大小.
result[i++] = left[0]; // 然后将小的元素存放在合并数组的对应位置中.
left = Arrays.copyOfRange(left, 1, left.length);
} else {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
}
while(left.length>0){ // 不满足以上while条件跳出循环时,执行,
result[i++] = left[0];
left = Arrays.copyOfRange(left,1,left.length);
}
while(right.length>0){
result[i++] = right[0];
right = Arrays.copyOfRange(right,1,right.length);
}
return result; // 返回排序合并后的序列.
}
/**
* 快速排序
*快速排序是分而治之的经典应用之一
* 通过递归调用的方式实现排序,
* 在大多情况下,其效率是最高的.
*/
public int[] sort(int[] arr){ // sort 方法 用来出copy数组,并调用排序方法.
int[] copyarr=Arrays.copyOf(arr,arr.length);
return quicksort(copyarr,0,copyarr.length-1);
}
// 快速排序方法.
private int[] quicksort(int[] arr,int left,int right){ //传入参数,待排序的数组,左下标,及数组长度减1.
if(left<right){ // if判断条件,这里没有else是因为left必然是小于right的.如果等于的话,直接返回数组就可以了.
int partitionindex = partition(arr,left,right); // 声明局部变量,调用分区方法,递归调用.
quicksort(arr,left,partitionindex-1); //
quicksort(arr,partitionindex+1,right); // 递归调用本身,
}
return arr;
}
/**
* 分区方法,将无序序列以基准为界分别放在左右两边,
* 真正的比较交换操作,是在这个分区方法里实现的.
* 然后在通过前面的递归调用,来循环使用分区方法,实现排序.
*/
private int partition(int[] arr,int left,int right){
int pivot =left;
int index = pivot+1;
for (int i=index;i<=right;i++){
if (arr[i]<arr[pivot]){
swap(arr,i,index);
index++;
}
}
swap(arr,pivot,index-1);
return index-1;
}
// 封装通用方法,将数组arr中的arr[i]与arr[j]的值交换
private void swap(int[] arr,int i,int j){
int temp = arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
-
算法的比较与使用
关于个排序算法的复杂度,稳定性,等信息的对比,可以参照下面这张图:
根据前面的学些了解的特性,最基本的三种排序,冒泡,选择,插入排序,在小规模数据的排序上,表现会好些,在序列趋近于正序时,冒泡和插入更高效,.
归并排序是最稳定的排序算法,其在不同情况下的时间复杂度不会有多大变化,而在对大量无序随机数排序时,快排的效率时最高的,但,归并排序和快速排序对内存有一定要求,不适合需要控制内存使用的情况.
更新时间:
2019-4-7
3:14