- 一丶冒泡排序
- 思想和代码
- 具体分析
- 二丶快速排序
- 具体思想和代码
- Hoare版
- 挖坑法
- 前后指针
- 关于优化
- 具体分析
冒泡排序可能是我们在JavaSE阶段第一个接触的算法，其基本思想就是：
从第一个开始遍历，然后如果当前元素大于下一个元素，那么交换两个元素的位置，这样就能确保一轮遍历下来最后一个元素就是当前元素集合的最大值。所以有多少个元素就遍历多少轮。
接着给出代码：
public static void swap(int[] arr,int left,int right){
int tmp = arr[left];
arr[left] = arr[right];
arr[right] = tmp;
}
public static void BubbleSort(int[] arr){
for(int i = arr.length;i > 0;i--){
for(int j = 1;j < i;j++){
if(arr[j] < arr[j - 1]){
swap(arr,j,j - 1);
}
}
}
}
具体分析
（1）关于时间复杂度
这里的时间复杂度，我们考虑最差情况，其实就是一个等差数列的前n项和。所以用大O阶表示就是O（n²）
（2）稳定性
很明显这里没有隔着元素进行交换，所以是稳定的。
二丶快速排序 具体思想和代码什么是快速排序呢？
快速排序是一个递归实现，如果单独把递归中某一层拉出来说，那就是找一个值key，然后把所有小于key的值放在右边，把所有大于key的值放在右边。那总的实现就是一直递归到最小元素集合，然后排好之后一层一层往回走，接着就有了有序版本。所以这样就有了我们的基础代码版本
如下:
public static void quickSort(int[] arr,int left,int right){
//确保最少有两个元素在排序
if(right - left > 1) {
int subscript = partition(arr, left, right);
//左边都小于sub[ , )
quickSort(arr, left, subscript);//注意这里的中间值是取
//右边都大于sub[ , )
quickSort(arr, subscript + 1, right);
}
}
public static int partition(int[] arr,int left,int right){
//确定作为比较值的下标，不要觉得这一步多余，这一步是为后面的优化打基础
int index = right - 1;
//等下即将返回的值
int key = arr[right - 1]; //定义比较元素
int begin = left;//左边从left开始
int end = right - 1;//右边从right - 1下标开始
while(begin < end){
while(begin < end && arr[begin] <= key){
begin++;
}
while(begin < end && arr[end] >= key){
end--;
}
if(begin != end) {
swap(arr, begin, end);
}
}
if(begin != right-1){
swap(arr, begin, right-1);
}
return begin;
}
public static void swap(int[] arr,int left,int right){
int tmp = arr[left];
arr[left] = arr[right];
arr[right] = tmp;
}
其实我们可以很轻易的发现，快速排序难点之一就在这个partation方法，也就是返回中间值并且进行排序的方法。
上面用的就是我们常用的几种排序方法之一
这一位大佬的思想就是：
把最后一位作为key来进行比较，然后前指针开始往后走，走到一个大于key的值停止，后面的指针再开始往前走，走到一个小于key的值，接着两个值交换，最后直到前指针等于后指针就停止，接着交换最后一个元素和前指针指向的元素。
public static int partition(int[] arr,int left,int right){
//注意这里可以改进的，就是这个index，不是多此一举
int index = right - 1;
//后面改进大家就知道为啥我这里这样定义了
int key = arr[right - 1]; //定义比较元素
int begin = left;//左边从left开始
int end = right - 1;//右边从right - 1下标开始
while(begin < end){
while(begin < end && arr[begin] <= key){
begin++;
}
while(begin < end && arr[end] >= key){
end--;
}
if(begin != end) {
swap(arr, begin, end);
}
}
if(begin != right-1){
swap(arr, begin, right-1);
}
return begin;
}
挖坑法
挖坑法的思想也很简单，和上面的很像
但是区别在哪里呢？就是我先把这个值保存起来，然后前指针开始走，走到大于key的值，直接用当前前指针的值覆盖此时后指针位置的值，然后后指针开始走，走到小于key的值的地方，用此时后指针的值覆盖前指针的值，然后前指针再开始走，就无限套娃，最后begin和end相遇，用保存的值覆盖此时begin的值。
public static int partition1(int[] arr,int left,int right){
int index = right - 1;
//等下即将返回的值
int key = arr[right - 1]; //定义比较元素
int begin = left;//左边从left开始
int end = right - 1;//右边从right - 1下标开始
while(begin < end){
while(begin < end && arr[begin] <= key){
begin++;
}
while(begin < end && arr[end] >= key){
end--;
}
if(begin != end) {
swap(arr, begin, end);
}
}
if(begin != right-1){
swap(arr, begin, right-1);
}
return begin;
}
这里承接上部分代码，就单单提供了一个新的方法
前后指针这种方法很巧，就单单是只从一段发起，就是前后指针都是从前往后走，我这里阐述一下基本原理。
假设cur是后指针，prev是前指针，那么cur先走，如果cur指向的元素大于0，那就继续往后走，如果说小于0，那么pre先要++，++之后如果和prev处于同一下标，那么cur就继续往后走，如果不是同一下标，那么交换了之后cur再往后走，不断循环。这样可以保证什么？保证cur和prev之间的元素永远是大于key的。到最后了，prev往前走一位，交换prev和cur的值。
下面是代码：
public static int partition3(int[] arr,int left,int right){
int index = right - 1;
int key = arr[right - 1];
int cur = left;
int prev = cur - 1;
while(cur < right){
if(arr[cur] < key && ++prev != cur){
swap(arr,cur,prev);
}
cur++;
}
if(++prev != cur){
swap(arr,prev,right - 1);
}
return prev;
}
关于优化
这里的优化我上面一直在提，就是关于key值的选取，我们是可以优化的。什么意思呢？
这样说，我们如果要对一个数组排升序，而这个数组恰好是 [9,8,7,6,5,4,3,2,1]这意味着为什么？是不是每一次左边没有值，这样就多递归了两倍的层次，为了解决这个问题我们怎么办呢？我们选择下标就好了，但是下标不能乱选，我们可以从开头，中间，末尾选三个元素，然后选择中间的那个值作为key。
具体代码如下：
public static int getMiddle(int[] array, int left, int right){
int mid = left + ((right-left)>>1);
if(array[left] < array[right-1]){
if(array[mid] < array[left]){
return left;
}else if(array[mid] > array[right-1]){
return right-1;
}else{
return mid;
}
}else{
if(array[mid] > array[left]){
return left;
}else if(array[mid] < array[right-1]){
return right-1;
}else{
return mid;
}
}
}
也就是说，index，也就是我们选取的key值的下标完全可以是前，中，后中中间的那个值，但是我们快速排序总是以最后一个值为比较基准的，那么我们怎么办呢？那就加一个判断就好了，如果index下标不是最后一位，也就是不是right - 1，那么我们交换 index和right - 1的值就好了，其他都不变。其实说了这么多，也就是把：
int mid = left + ((right-left)>>1);
给变成：
int index = getIndexOfMiddle(array, left, right);
if(index != right-1){
swap(array, index, right-1);
}
具体分析
（1）时间复杂度
最坏情况是什么呢？
就是每一趟都比满，最后其实也就是一个等差数列的前n项和，用大O阶表示也就是：
O
(
n
2
)
color{red}{O(n^2)}
O(n2)
(2)稳定性
基本都是搁着元素进行交换，所以不稳定
