排序算法3_冒泡排序、快速排序

一、冒泡排序

1.1 冒泡排序定义和思路

 冒泡排序的基本思想是：通过相邻两个元素之间的比较和交换，使较大的元素逐渐从前面移向后面（升序），就像水底下的气泡一样逐渐向上冒泡，所以被称为“冒泡”排序。
 在生活中，扑克牌的排序就是应用了冒泡排序，从第二个扑克开始和它前面相邻的扑克比较，比它大则不动，比它小交换位置。这样我们在第一轮排序中可以得到最大的扑克牌，因为最大值是一直在向后传递，直到传到最后，那个值必然是扑克牌中最大的值。

2.2 冒泡排序实例代码

import java.util.Arrays;public class BubbleSort {public static void bubbleSort(int[] array){for (int i = 0; i < array.length-1; i++) {boolean fig = false; //如果 fig 为 true,则不需要交换for (int j = 0; j < array.length-1-i; j++) {  优化-iif (array[j+1] < array[j]){int tmp =array[j];array[j] = array[j+1];array[j+1] = tmp;fig = true;   //如果，如果fig 为true,则每次都需要交换}}if (!fig){break;}}}public static void main(String[] args) {int[] arr = {64, 34, 25, 12, 22, 11, 40};bubbleSort(arr);for (int i = 0; i < arr.length; i++) {System.out.print(arr[i]+" ");}}
}--------------------------------------------------------
输出结果：11 12 22 25 34 40 64 

冒泡排序算法分析：

冒泡排序的最坏时间复杂度为O(n^2)，
如果加了优化，时间复杂度最好为O（N）   
空间复杂度：O（1）  
稳定性：稳定  
优化：每一趟都需要判断 上一次 有没有交换

二、快速排序

 快速排序及算法实现 快速排序(Quick Sort) 是对冒泡排序的一种改进方法，在冒泡排序中，进行元素的比较和交换是在相邻元素之间进行的，元素每次交换只能移动一个位置，所以比较次数和移动次数较多，效率相对较低。

2.1 快速排序定义和思路

 在快速排序中，元素的比较和交换是从两端向中间进行的，较大的元素一轮就能够交换到后面的位置，而较小的元素一轮就能交换到前面的位置，元素每次移动的距离较远，所以比较次数和移动次数较少，速度较快，故称为“快速排序”。
 任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

排序步骤：

1. 选择第一个数2作为基准key，定义低位指针low，和高位指针high，此时low位于0，high位于4
2. 从高位开始和基准比较，首先是4，4>2,符合高位定义，4保持不动；
3. high指针-1=3，array[3]=1<2,此时1需换到低位，和array[0]置换位置，此时的数组为{1,5,3,1,4}；
4. low指针+1=1，array[1]=5>2,此时5需换到高位，和array[3]置换位置，此时数组为{1,5,3,5,4}；
5. high指针-1=2,array[2]=3>2,3保持不变，此时数组为{1,5,3,5,4}；
6. high指针-1=1，此时high指针==low指针，结束第一轮内循环比较，将key=2放置array[1]的位置，此时数组为{1,2,3,5,4}
7. 然后会对2之前的数{1}以及2之后的数{3,5,4}递归，继续按照上述规则排序直到所有的子数组都排序完成。

2.2 快速排序实例代码

public static void quick(int[] array,int start,int end){if (start >= end){return;}int pivot = partitionHole(array,start,end);quick(array,start,pivot-1);quick(array,pivot+1,end);}private static int partitionHoare(int[] array, int left, int right) {int tmp = array[left];int i = left;while (left <right) {//单独循环，不能一直超过左边的边界while (left < right && array[right] >= tmp) {right--;}while (left < right && array[left] <= tmp) {left++;}swap(array, left, right);}swap(array,i,left);return left;}

```bash
/*** 快速排序—————挖坑法* @param array* @param left* @param right* @return*/private static  int partitionHole(int[] array,int left ,int right){int tmp = array[left];while (left <right){while (left<right && array[right] >= tmp){right--;}array[left] = array[right];while (left < right && array[left] <= tmp) {left++;}array[right] = array[left];}array[left] = tmp;return left;}
`
```bash

*** 前后指针法* @param array* @param left* @param right* @return*/private static int partition(int[] array, int left, int right) {int prev = left ;int cur = left+1;while (cur <= right) {if(array[cur] < array[left] && array[++prev] != array[cur]) {swap(array,cur,prev);}cur++;}swap(array,prev,left);return prev;}public static void quickSort(int[]array) {quick(array,0,array.length-1);}

快速排序算法分析

时间复杂度：最好情况下O（N*logN）；最坏情况下下O（N^2）
空间复杂度 最好情况下O(logN) ; 最坏情况下O(N)
稳定性:稳定