常见排序算法总结 -- java实现

排序算法可以分为两大类：

1. 非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。
2. 线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。

相关概念

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
• 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
• 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
• 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

一、插入排序

1.1 直接插入排序

  插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。

直接插入排序的算法思路：

1. 设置监视哨temp，将待插入记录的值赋值给temp；
2. 设置开始查找的位置j；
3. 在数组arr中进行搜索，搜索中将第j个记录后移，直至temp≥arr[j]为止；
4. 将temp插入arr[j+1]的位置上。

/**  * 直接插入排序  */ public void insertSort(int[] arr) {     //外层循环确定待比较数值     //必须i=1，因为开始从第二个数与第一个数进行比较     for (int i = 1; i < arr.length; i++) {         //待比较数值         int temp = arr[i];         int j = i - 1;         //内层循环为待比较数值确定其最终位置         //待比较数值比前一位置小，应插往前插一位         for (; j >= 0 && arr[j] > temp; j--) {             //将大于temp的值整体后移一个单位             arr[j + 1] = arr[j];         }         //待比较数值比前一位置大，最终位置无误         arr[j + 1] = temp;     } }

1.2 希尔排序

  希尔排序(Shell's Sort)是插入排序的一种，又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。

希尔排序的算法思路：

1. 把数组按下标的一定增量分组；
2. 对每组使用直接插入排序算法排序；
3. 随着增量逐渐减少，每组包含的值越来越多，当增量减至1时，整个文件被分成一组，算法便终止。

/**  * 希尔排序  */ public void shellSort(int[] arr) {     int d = arr.length;     while (d >= 1) {         d = d / 2;         for (int x = 0; x < d; x++) {             //按下标的一定增量分组然后进行插入排序             for (int i = x + d; i < arr.length; i = i + d) {                 int temp = arr[i];                 int j;                 for (j = i - d; j >= 0 && arr[j] > temp; j = j - d) {                     //移动下标                     arr[j + d] = arr[j];                 }                 arr[j + d] = temp;             }         }     } } 

二、交换排序

2.1 冒泡排序

  在一组数据中，相邻元素依次比较大小，最大的放后面，最小的冒上来。

冒泡排序算法的算法思路：

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

/**  * 冒泡排序  */ public void bubbleSort(int[] arr) {     for (int i = 0; i < arr.length - 1; i++) {         

                    

                        
关键字：