快速排序-排序算法(五)

向右看齐 2023-03-01 12:27 15阅读 0赞

## 快速排序 ##

### 前言 ###

*  先从数列中取出一个数作为key值；
 *  将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
 *  对左右两个小数列重复第二步，直至各区间只有1个数。

### 基本思想 ###

1.  初始时 i = 0; j = 9; key=72

1.  由于已经将a\[0\]中的数保存到key中，可以理解成在数组a\[0\]上挖了个坑，可以将其它数据填充到这来。
2.  从j开始向前找一个比key小的数。当j=8，符合条件，a\[0\] = a\[8\] ; i++ ; 将a\[8\]挖出再填到上一个坑a\[0\]中。

1.  这样一个坑a\[0\]就被搞定了，但又形成了一个新坑a\[8\]，这怎么办了？简单，再找数字来填a\[8\]这个坑。
2.  这次从i开始向后找一个大于key的数，当i=3，符合条件，a\[8\] = a\[3\] ; j-- ; 将a\[3\]挖出再填到上一个坑中。

1.  此时 i = 3; j = 7; key=72  
    再重复上面的步骤，先从后向前找，再从前向后找。  
    从j开始向前找，当j=5，符合条件，将a\[5\]挖出填到上一个坑中，a\[3\] = a\[5\]; i++;
2.  从i开始向后找，当i=5时，由于i==j退出。  
    此时，i = j = 5，而a\[5\]刚好又是上次挖的坑，因此将key填入a\[5\]。
3.  可以看出a\[5\]前面的数字都小于它，a\[5\]后面的数字都大于它。因此再对a\[0…4\]和a\[6…9\]这二个子区间重复上述步骤就可以了。

### 代码实现 ###

public class 快速排序 { 
        public static void main(String[] args) { 
            int[] arr = new int[]{ 59, 20, 17, 13, 28, 14, 23, 83};
            quickSort(arr, 0, arr.length-1);
            for (int i : arr) System.out.println(i);
        }
    
        public static void quickSort(int a[], int l, int r) { 
            if (l >= r) { 
                return;
            }
            int i = l, j = r, key = a[l];
            while (i < j) { 
                while (i < j && a[j] > key)
                    j--;
                if (i < j)
                    a[i++] = a[j];
                while (i < j && a[i] < key)
                    i++;
                if (i < j)
                    a[j--] = a[i];
            }
            // i==j
            a[i] = key;
            quickSort(a, l, i - 1);
            quickSort(a, i + 1, r);
        }
    }

### 算法特点 ###

*  时间复杂度O（N\*logN）
 *  额外空间复杂度O（1）
 *  不稳定，替换过程，相等数值会替换位置