一、冒泡排序
先来看原理部分,**冒泡排序就是将每个数与它后面的数进行比较，如果大于之后的数，就两者交换，一直循环前面的操作，直到该数小于后面的数为止**。<br />
一、代码
public class Solution {public static void main(String[] args){int[] arr = new int[] {6,4,8,3,5,9,4,2,7,1,6};bubbleSort(arr);for(int i = 0;i<arr.length;i++) {System.out.println(arr[i]);}}public static int[] bubbleSort(int[] arr) {for(int i = 0;i<arr.length-1;i++){for(int j = 0;j<arr.length-i-1;j++) {if(arr[j]>arr[j+1]){int temp = arr[j+1];arr[j+1] = arr[j];arr[j] = temp;}}}return arr;}}
二、算法分析
1、冒泡排序算法的性能
2、时间复杂度
若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值：Cmin = N - 1, Mmin = 0。所以，冒泡排序最好时间复杂度为O(N)。
但是上述代码，不能扫描一趟就完成排序，它会进行全扫描。所以一个改进的方法就是，当冒泡中途发现已经为正序了，便无需继续比对下去。改进方法一会儿介绍。
若初始文件是反序的，需要进行 N -1 趟排序。每趟排序要进行 N - i 次关键字的比较(1 ≤ i ≤ N - 1)，且每次比较都必须移动记录三次(内层for循环里的三次交换看代码)来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：
Cmax = N(N-1)/2 = O(N^2)
Mmax = 3N(N-1)/2 = O(N^2)
冒泡排序的最坏时间复杂度为O(N^2)。
因此，冒泡排序的平均时间复杂度为O(N^2)。
总结起来，其实就是一句话：当数据越接近正序时，冒泡排序性能越好。
3、算法稳定性
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
冒泡排序就是把小的元素往前调或者把大的元素往后调。是相邻的两个元素的比较，交换也发生在这两个元素之间。所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
四、优化
对冒泡排序常见的改进方法是加入标志性变量exchange，用于标志某一趟排序过程中是否有数据交换。
如果进行某一趟排序时并没有进行数据交换，则说明所有数据已经有序，可立即结束排序，避免不必要的比较过程。
public class Solution {public static void main(String[] args){int[] arr = new int[] {6,4,8,3,5,9,4,2,7,1,6};bubbleSort(arr);for(int i = 0;i<arr.length;i++) {System.out.println(arr[i]);}}public static int[] bubbleSort(int[] arr) {for(int i = 0;i<arr.length-1;i++){boolean flag = false;//优化部分for(int j = 0;j<arr.length-i-1;j++) {if(arr[j]>arr[j+1]){int temp = arr[j+1];arr[j+1] = arr[j];arr[j] = temp;flag = true;}}if(flag == false)break;}return arr;}}
二、快速排序
快速排序的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分：分割点左边都是比它小的数，右边都是比它大的数。
然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
通过图来写代码
一、代码
public static int division(int[] arr,int left,int right) {int base = arr[left];while(left<right){while(left<right&&arr[right]>=base){right--;}arr[left] = arr[right];while(left<right&&arr[left]<=base){left++;}arr[right] = arr[left];}arr[left] = base;return left;}public static void quickSort(int[] arr,int left,int right){if(left<right){int index = division(arr, left, right);quickSort(arr, left, index-1);quickSort(arr, index+1, right);}}
二、算法分析
1、快速排序算法的性能
2、时间复杂度
当数据有序时，以第一个关键字为基准分为两个子序列，前一个子序列为空，此时执行效率最差。
而当数据随机分布时，以第一个关键字为基准分为两个子序列，两个子序列的元素个数接近相等，此时执行效率最好。
所以，数据越随机分布时，快速排序性能越好；数据越接近有序，快速排序性能越差。
3、空间复杂度
快速排序在每次分割的过程中，需要 1 个空间存储基准值。而快速排序的大概需要 logN次的分割处理，所以占用空间也是 logN 个。
4、算法稳定性
在快速排序中，相等元素可能会因为分区而交换顺序，所以它是不稳定的算法。
三、选择排序
选择排序的原理就是，每次从无序的序列中循环选出最小的数，将它交换到无序序列的最前面，最终在数组中形成一个从前往后排列的有序序列。
一、代码
public static int[] selectSort(int[] arr) {int index = 0;for(int i = 0;i<arr.length;i++){int temp = arr[i];for(int j = i+1;j<arr.length;j++){if(arr[j]<temp){temp = arr[j];index = j;}}arr[index] = arr[i];arr[i] = temp;}return arr;}
二、算法分析
1、简单算法排序性能
2、时间复杂度
简单选择排序的比较次数与序列的初始排序无关。 假设待排序的序列有 N 个元素，则比较次数总是N (N - 1) / 2。
而移动次数与序列的初始排序有关。当序列正序时，移动次数最少，为 0.
当序列反序时，移动次数最多，为3N (N - 1) / 2。
所以，综合以上，简单排序的时间复杂度为 O(N^2)。
3、空间复杂度
简单选择排序需要占用 1 个临时空间，用于保存最小值得索引。
四、插入排序
插入排序和选择排序有点类似，都是把序列前面的部分看成有序的序列，后面部分看成无序的序列。每次会选定无序序列中第一个元素，插入到有序序列中的合适位置，随着有序序列的长度不断增加，最终形成一个完全的有序序列。
**
一、代码
public static void insertSort(int[] arr){for(int i = 1;i<arr.length;i++){int temp = arr[i];// int k = i;int j;for(j = i-1;j>=0&&arr[j]>temp;j--) {arr[j+1] = arr[j];// if(arr[k]<arr[j])// {// int temp = arr[j];// arr[j] = arr[k];// arr[k] = temp;// k--;// }}arr[j+1] = temp;}}
二、算法分析
1、直接插入排序的算法性能
2、时间复杂度
当数据正序时，执行效率最好，每次插入都不用移动前面的元素，时间复杂度为O(N)。
当数据反序时，执行效率最差，每次插入都要前面的元素后移，时间复杂度为O(N^2)。
所以，数据越接近正序，直接插入排序的算法性能越好。
3、空间复杂度
由直接插入排序算法可知，我们在排序过程中，需要一个临时变量存储要插入的值，所以空间复杂度为 1 。
4、算法稳定性
直接插入排序的过程中，不需要改变相等数值元素的位置，所以它是稳定的算法。
5、优化
因为在一个有序序列中查找一个插入位置，以保证有序序列的序列不变，所以可以使用二分查找，减少元素比较次数提高效率。
二分查找是对于有序数组而言的，假设如果数组是升序排序的。那么，二分查找算法就是不断对数组进行对半分割，每次拿中间元素和目标数字进行比较，如果中间元素小于目标数字，则说明目标数字应该在右侧被分割的数组中，如果中间元素大于目标数字，则说明目标数字应该在左侧被分割的数组中。
public static void insertSort(int[] arr){for(int i = 1;i<arr.length;i++){int temp = arr[i];int left = 0;int right = i - 1;int j = i - 1;//二分法找到大于等于要查找值的小标while (left < right){int middle = left + ((right - left) / 2);if (arr[middle] > temp){right = middle - 1;}else{left = middle + 1;}}//将left到j的值后移,while(j>=left) {arr[j+1] = arr[j];j--;}arr[j+1] = temp;}}
五、希尔排序
一、代码
public static void shellSort(int[] arr){int step = arr.length/2;while(step>0){for(int i = step;i<arr.length;i++){for(int j = i;j>=step&&arr[j]<arr[j-step];j-=step){int temp = arr[j];arr[j] = arr[j-step];arr[j-step] = temp;}}step/=2;}}
二、算法分析
1、时间复杂度
步长的选择是希尔排序的重要部分，只要最终步长为1任何步长序列都可以工作。
算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。当步长为1时，算法变为插入排序，这就保证了数据一定会被排序。
步长序列的不同，会导致最坏的时间复杂度情况的不同。
本文中，以N/2为步长的最坏时间复杂度为N^2。
Donald Shell 最初建议步长选择为N/2并且对步长取半直到步长达到1。虽然这样取可以比O(N^2)类的算法（插入排序）更好，但这样仍然有减少平均时间和最差时间的余地。可能希尔排序最重要的地方在于当用较小步长排序后，以前用的较大步长仍然是有序的。比如，如果一个数列以步长5进行了排序然后再以步长3进行排序，那么该数列不仅是以步长3有序，而且是以步长5有序。如果不是这样，那么算法在迭代过程中会打乱以前的顺序，那就不会以如此短的时间完成排序了。
用这样步长序列的希尔排序比插入排序要快，甚至在小数组中比快速排序和堆排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。
2、算法稳定性
希尔排序中相等数据可能会交换位置，所以希尔排序是不稳定的算法。
3、直接插入排序和希尔排序的比较
直接插入排序是稳定的；而希尔排序是不稳定的。
直接插入排序更适合于原始记录基本有序的集合。
希尔排序的比较次数和移动次数都要比直接插入排序少，当N越大时，效果越明显。
希尔排序的比较次数和移动次数都要比直接插入排序少，当N越大时，效果越明显。
直接插入排序也适用于链式存储结构；希尔排序不适用于链式结构。
六、归并排序
归并排序首先将序列看成一个个长度为 1 的有序序列，然后将相邻的两个序列归并，形成一个按照大小排好序的长度为 2 的有序序列。以此类推，最后形成完全有序的一个序列。<br />**<br />
一、代码
public static void mergeSort(int[] list) {if (list.length > 1) {int[] leftHalf = new int[list.length / 2];System.arraycopy(list, 0, leftHalf, 0, list.length / 2);mergeSort(leftHalf);int rightHalfLength = list.length - list.length / 2;int[] rightHalf = new int[rightHalfLength];System.arraycopy(list, list.length / 2, rightHalf, 0, rightHalfLength);mergeSort(rightHalf);int[] temp = merge(leftHalf, rightHalf);System.arraycopy(temp, 0, list, 0, temp.length);}}public static int[] merge(int[] leftHalf, int[] rightHalf) {int[] temp = new int[leftHalf.length + rightHalf.length];int firstIndex = 0;int secondIndex = 0;int tempIndex = 0;while (firstIndex < leftHalf.length && secondIndex < rightHalf.length) {if (leftHalf[firstIndex] < rightHalf[secondIndex]) {temp[tempIndex++] = leftHalf[firstIndex++];} else {temp[tempIndex++] = rightHalf[secondIndex++];}}while (firstIndex < leftHalf.length) {temp[tempIndex++] = leftHalf[firstIndex++];}while (secondIndex < rightHalf.length) {temp[tempIndex++] = rightHalf[secondIndex++];}return temp;}
二、算法分析
1、归并排序算法的性能
2、时间复杂度
归并排序的形式就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的可以得出它的时间复杂度是O(n*log2n)。
3、空间复杂度
由前面的算法说明可知，算法处理过程中，需要一个大小为n的临时存储空间用以保存合并序列。
4、算法稳定性
在归并排序中，相等的元素的顺序不会改变，所以它是稳定的算法。
5、归并排序和堆排序、快速排序的比较
若从空间复杂度来考虑：首选堆排序，其次是快速排序，最后是归并排序。
若从稳定性来考虑，应选取归并排序，因为堆排序和快速排序都是不稳定的。
若从平均情况下的排序速度考虑，应该选择快速排序。
七、堆排序
所以堆排序的原理就是**首先建立一个大根堆，然后每次移除堆顶元素，再把剩下的元素重新调整成大根堆的过程。因为堆顶是最大的元素，所以每次移除出来的一个个堆顶就构成了一个从大到小排好序的序列**。<br />可以看到，堆排序的关键就在于**构建堆**与**移除堆顶后的调整堆**。<br /><br />
一、代码
//建立一个内部类Heapprivate class Heap{//用一个List来存放堆中的元素List<Integer> list = new ArrayList();//构造函数，将传入的数组最终构建成大根堆private Heap(int[] array) {for (int i = 0; i < array.length; i++) {add(array[i]);}}/*** 功能：每次先把传入的元素放在堆尾，然后调整，变成一个元素个数多一的大根堆* @param num 传入的元素*/private void add(int num) {list.add(num); //先将传入的元素追加在堆尾int currentIndex = list.size() - 1; //从堆尾开始遍历while (currentIndex > 0) {int parentIndex = (currentIndex - 1) / 2; //先找到堆尾元素的父节点//因为我们要构建的是大根堆，所以当父节点小于当前节点时，两者交换。// 否则说明刚刚追加的元素合适，直接退出循环if ((list.get(currentIndex).compareTo(list.get(parentIndex))) > 0) {int temp = list.get(currentIndex);list.set(currentIndex, list.get(parentIndex));list.set(parentIndex, temp);//两者交换后，我们要继续判断新追加的节点是不是比刚才的父节点的父节点还要大，// 所以将刚才父节点的索引赋值给它，继续刚才的循环currentIndex = parentIndex;} else {break;}}}/*** 每次移除大根堆的堆顶元素，然后调整，变成一个元素个数减一的大根堆* @return 返回的大根堆堆顶元素*/private int remove() {int removedNum = list.get(0); //先保存堆顶元素//将堆尾元素赋值给堆顶，同时删除堆尾list.set(0, list.get(list.size() - 1));list.remove(list.size() - 1);//要开始调整堆了，首先从新堆顶开始遍历int currentIndex = 0;while (currentIndex < list.size() - 1) {int leftIndex = currentIndex * 2 + 1;int rightIndex = currentIndex * 2 + 2; //先找到当前节点的左右孩子if (!(leftIndex < list.size())) { //如果不存在左孩子，说明当前节点已经最大，不需要调整大根堆，直接退出循环break;}int maxIndex = leftIndex; //如果存在左孩子，先假设它是最大的节点//如果右孩子也存在的话，那么就要让它跟左孩子比较一下谁最大了if (rightIndex < list.size()) {if ((list.get(maxIndex).compareTo(list.get(rightIndex))) < 0) {maxIndex = rightIndex;}}//用刚才得到的，左右孩子中的最大节点，与当前节点进行比较//如果当前节点比最大节点还要大的话，说明当前节点已经最大，不需要调整大根堆，直接退出循环//否则，交换if ((list.get(currentIndex).compareTo(list.get(maxIndex))) > 0) {break;} else {int temp = list.get(currentIndex);list.set(currentIndex, list.get(maxIndex));list.set(maxIndex, temp);currentIndex = maxIndex;}}return removedNum; //返回之前保存的堆顶元素}}
因为我们的算法是堆排序，所以上面的代码是一个实现堆（Heap）的内部类，其中 add 方法用来建堆，就如同动画里面演示的。delete 方法用于删除堆顶和调整堆。
下面是堆排序的调用方法
public void heapSort(int[] list) {//根据数组构建一个大根堆Heap heap = new Heap(list);//每次移除堆顶的最大元素，赋给数组（因为我们最后要的数组是从小到大排列的，所以从后遍历）。for (int i = list.length - 1; i >= 0; i--) {list[i] = heap.remove();}}
二、算法分析
1、堆排序算法的总体情况
2、时间复杂度
n 个结点，从第 0 层至第 logn 层。对于第 i 层的 2i 个点如果需要往下走 logn−i 步，那么把走的所有步相加得：
HeapAdjust() 耗时 logn，共 n 次，故排序时间为 O(nlogn)。
堆的存储表示是顺序的。因为堆所对应的二叉树为完全二叉树，而完全二叉树通常采用顺序存储方式。
当想得到一个序列中第k个最小的元素之前的部分排序序列，最好采用堆排序。
3、算法稳定性
堆排序是一种不稳定的排序方法。
因为在堆的调整过程中，关键字进行比较和交换所走的是该结点到叶子结点的一条路径，因此对于相同的关键字就可能出现排在后面的关键字被交换到前面来的情况。
若有收获，就点个赞吧
0 人点赞
