package com.itheima;

import java.util.Arrays;
import java.util.regex.Pattern;

/**
* 4、 请列举您了解的一些排序算法，并用Java语言实现一个效率较高的。
*/
public class Test4 {
        /*
         * 1、选择排序 2、冒泡排序 3、快速排序
         *
         */
       
        public static void main(String[] args) {
                int arr[] = { 6, 2, 7, 3, 8, 5, 9 };//{5,2,7,3,8,6,9} r=5 l=1  //{5,2,6,3,8,7,9} l=2 r=4{} //{5,2,3,6,8,7,9} l=3 r=3
                quickSort(arr, 0, arr.length - 1);
                System.out.println(Arrays.toString(arr));
        }
        //快速排序算法
        public static void quickSort(int arr[], int low, int high) {
                int left = low;                //设置左侧索引
                int right = high;        //设置右侧索引
                int x = arr[low];        //设置标准值

                while (left < right) {        //当左右索引相同时，为一个循环
                        while (left < right && x <= arr[right])
                                right--;        //从右侧找到第一个小于标准值的数
                        //交换
                        if (left < right) {
                                int temp = arr[right];
                                arr[right] = arr[left];
                                arr[left] = temp;
                                left++;                //减少比较次数
                        }

                        while (left < right && x >= arr[left])
                                left++;        //从左侧找到第一个大于标准值的数
                        //交换
                        if (left < right) {
                                int temp = arr[right];
                                arr[right] = arr[left];
                                arr[left] = temp;
                                right--;                //减少比较次数
                               
                        }
                        //每次循环后分成左右2块，对2块递归调用快速排序
                        if (left > low)
                                quickSort(arr, low, right - 1);
                        if (right < high)
                                quickSort(arr, right + 1, high);
                }
        }
}
快速排序的效率远高于 常用的冒泡和选择排序，就学习了一下

他的思想是：右挖坑 左挖坑 直到左右索引相同。这样就完成了一次循环，使数组分成了左右两边，左边的都小于参考值，右边的都大于参考值，再用递归调用多次就能完全排序。

1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A互换；
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A，将A和A[j]互换；
5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。

package com.itheima;

import java.util.Arrays;
import java.util.regex.Pattern;

/**
* 4、 请列举您了解的一些排序算法，并用Java语言实现一个效率较高的。
*/
public class Test4 {
        /*
         * 1、选择排序 2、冒泡排序 3、快速排序
         *
         */
       
        public static void main(String[] args) {
                int arr[] = { 6, 2, 7, 3, 8, 5, 9 };//{5,2,7,3,8,6,9} r=5 l=1  //{5,2,6,3,8,7,9} l=2 r=4{} //{5,2,3,6,8,7,9} l=3 r=3
                quickSort(arr, 0, arr.length - 1);
                System.out.println(Arrays.toString(arr));
        }
        //快速排序算法
        public static void quickSort(int arr[], int low, int high) {
                int left = low;                //设置左侧索引
                int right = high;        //设置右侧索引
                int x = arr[low];        //设置标准值

                while (left < right) {        //当左右索引相同时，为一个循环
                        while (left < right && x <= arr[right])
                                right--;        //从右侧找到第一个小于标准值的数
                        //交换
                        if (left < right) {
                                int temp = arr[right];
                                arr[right] = arr[left];
                                arr[left] = temp;
                                left++;                //减少比较次数
                        }

                        while (left < right && x >= arr[left])
                                left++;        //从左侧找到第一个大于标准值的数
                        //交换
                        if (left < right) {
                                int temp = arr[right];
                                arr[right] = arr[left];
                                arr[left] = temp;
                                right--;                //减少比较次数
                               
                        }
                        //每次循环后分成左右2块，对2块递归调用快速排序
                        if (left > low)
                                quickSort(arr, low, right - 1);
                        if (right < high)
                                quickSort(arr, right + 1, high);
                }
        }
}
快速排序的效率远高于 常用的冒泡和选择排序，就学习了一下

他的思想是：右挖坑 左挖坑 直到左右索引相同。这样就完成了一次循环，使数组分成了左右两边，左边的都小于参考值，右边的都大于参考值，再用递归调用多次就能完全排序。

1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A互换；
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A，将A和A[j]互换；
5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。