首页 > 代码库 > 数据结构-简单排序

数据结构-简单排序

在我们的业务中,有很多情况都需要根据某种需要针对要返回的数据进行排序,但是排序是一种非常耗时的操作,特别是当数据量大的时候,所有有时候我们也会说,数据的排序是很重要的,但是也是非常耗时间的。在这里简单介绍一下简单排序,这些排序算法执行速度较慢,但算法逻辑简单,在某些时候,比其他的复杂排序算法更加有效,同时也能帮助我们理解其他的复杂排序算法。

一、冒泡排序

 冒泡算法的排序规则:重复比较相邻的两个元素,如果第一个比第二个大,就交换两个元素的位置,重复这个动作,就可以将最大值移动到后面。一趟(从第一个要比较的元素到最后一个要比较的元素)可以选择出一个未比较的数列中最大的元素,重复到最后没有要比较的元素的时候,完成排序。

冒泡算法的步骤如下:

  • 计算出要排序的数组a的大小n,数组下标从0开始。
  • 设置一个标志位标识已经排序的数组下标位置,即i=n-1(表示还没有开始排序)。
  • 令j=0,1,2.....i-1,循环比较a[j]和a[j+1]的大小,如果a[j]>a[j+1],那么交换两者的值。
  • 令i=i-1,循环进行上一步的处理,直到i<0为止。  

 时间复杂度:

  不管数组初始状态是什么样的,都需要进行n-1趟排序,每趟排序比较n-j次比较,如果初始状态是排序好的,那么移动次数为0。如果初始状态是反序的,那么每次比较移动3次。计算时间负责度计算式如下:假设比较次数C和移动次数M。

  Cmin = n(n-1)/2 = O(n2), Mmin = 0

  Cmax = n(n-1)/2 = O(n2), Mmax = 3n(n-1)/2 = O(n2)

  所以时间复杂度比较为O(n2)

代码如下:

技术分享
 1   /** 2      * 冒泡排序<br/> 3      * 不变性,在坐标大于i的部分永远是有序的,也就是说在排序过程中不会改变此部分的排列 4      *  5      * @param array 6      */ 7     public void bubbleSort(double[] array) { 8         if (array == null || array.length < 2) { 9             return;10         }11 12         int size = array.length;13         for (int i = size - 1; i >= 0; i--) {14             for (int j = 0; j < i; j++) {15                 if (Double.compare(array[j], array[j + 1]) > 0) {16                     // swap the datas17                     array[j] = array[j] + array[j + 1];18                     array[j + 1] = array[j] - array[j + 1];19                     array[j] = array[j] - array[j + 1];20                 }21             }22         }23     }
Bubble Sort Code

针对冒泡排序有一种变种,下面这段代码,在选择出最大值后,会将数组中的未排序的最小值移动到数组的前端。

技术分享
 1     /** 2      * 冒泡排序<br/> 3      * 不变性,在坐标大于i的部分永远是有序的,也就是说在排序过程中不会改变此部分的排列 4      *  5      * @param array 6      */ 7     public void twoWayBubbleSort(double[] array) { 8         if (array == null || array.length < 2) { 9             return;10         }11 12         int left = 0;13         int right = array.length - 1;14         for (int i = right; i >= left; i--) {15             int j = left;16 17             for (; j < i; j++) {18                 if (Double.compare(array[j], array[j + 1]) > 0) {19                     // swap the datas20                     array[j] = array[j] + array[j + 1];21                     array[j + 1] = array[j] - array[j + 1];22                     array[j] = array[j] - array[j + 1];23                 }24             }25 26             for (j = j - 1; j > left; j--) {27                 if (Double.compare(array[j - 1], array[j]) > 0) {28                     // swap the datas29                     array[j] = array[j] + array[j - 1];30                     array[j - 1] = array[j] - array[j - 1];31                     array[j] = array[j] - array[j - 1];32                 }33             }34             left++;35         }36     }
View Code

 

二、选择排序

选择排序是针对冒泡排序的一种改进,交换次数从O(n2)降低到O(n),但是比较次数还是O(n2)。在java语言中,这个优化性能相对于冒泡排序不高,但是在其他操作内存的语言中,选择排序比冒泡排序还是有很大的速度改进的。java语言交换值只是更改引用,没有操作内存的移动等底层操作,所有影响不大。

选择排序规则:和冒泡排序一样,只是将每趟排序中,不进行数据的交换,只是选择处理最大元素的位置,即下标。

选择排序的算法:

  • 将数组分成两个区域:有序区和无序区,初始状态是有序区为空,无序区为a[1...n]。
  • 进行第i(0<i<n)趟排序,在无序区a[i,n]中选择一个最大值,即a[k],将a[k]和a[i]交换值。
  • i++,将a[1...i-1]设置为有序区,将a[i...n]设置成无序区,循环进行上一步操作,直到i=n结束排序。

时间复杂度和冒泡排序一样,平均复杂度是O(n2)。

实现代码如下:

技术分享
 1     /** 2      * 选择排序<br/> 3      * 不变性,在坐标小于i的部分永远是有序的,也就是说在排序过程中不会改变此部分的排列 4      *  5      * @param array 6      */ 7     public void selectSort(double[] array) { 8         if (array == null || array.length < 2) { 9             return;10         }11 12         int size = array.length;13         int minindex = 0;14         double tmpvalue = http://www.mamicode.com/-1;15 16         for (int i = 0; i < size; i++) {17             minindex = i;18             for (int j = i + 1; j < size; j++) {19                 if (Double.compare(array[minindex], array[j]) > 0) {20                     minindex = j;21                 }22             }23 24             // swap the datas25             tmpvalue =http://www.mamicode.com/ array[i];26             array[i] = array[minindex];27             array[minindex] = tmpvalue;28         }29     }
Select Sort Code

 

三、插入排序

插入排序的规则:将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间负责度还是O(n2),是一种稳定排序算法。

插入排序的算法:

  • 将要排序的数组分成两组,分别是排序好的和未排序的,初始状态为:排序好的集合为a[0],未排序的为a[1...n-1]。
  • 在第i(0<i<n)趟排序中,从未排序的列表a[i...n]中选择第一个元素a[i],将其插入到排序号的列表中去,插入后排序号的列表还是有序的。形成排序好的集合为a[0...i],为排序的集合为a[i+1...n-1]。循环处理直到i=n为止。结束排序操作。

时间负责度还是O(n2)

实现代码如下:

技术分享
 1   /** 2      * 插入排序,主要是局部有序。 3      *  4      * @param array 5      */ 6     public void insertSort(double[] array) { 7         if (array == null || array.length < 2) { 8             return; 9         }10 11         int size = array.length;12         int j = 0;13         for (int i = 0; i < size; i++) {14             double tmpvalue =http://www.mamicode.com/ array[i];15             j = i;16             while (j > 0 && Double.compare(array[j - 1], tmpvalue) > 0) {17                 array[j] = array[--j];18             }19             array[j] = tmpvalue;20         }21     }
Insert Sort Code

 

数据结构-简单排序