算法入门学习----2.2快速排序

梦里梦外; 2022-06-01 11:59 179阅读 0赞

# 一、快速排序的实现原理 #

![SouthEast][]

与归并排序一样，采用了分治的思想。不过不是先分后治，而是**先治后分**。

**定义两个指针**：数组的左指针（left），数组的右指针（right），并用一个数（temp）保存第一个数。

**先将右指针往左依次遍历并和temp比较：**

如果arr\[right\]比temp大，那么右指针左移一位。

如果arr\[right\]比temp小，那么把arr\[left\]赋值等于arr\[right\]。

**接着开始遍历左指针并和temp比较：**

如果arr\[left\]比temp小，那么左指针右移一位。

如果arr\[left\]比temp大，那么把arr\[right\]赋值等于arr\[left\]。

**接着开始遍历右指针并和temp比较（进入循环）。。。。。**

**当左指针和右指针指向同一个数的时候，将这个数赋值为temp，第一次分结束。**

**进入递归：**将第一次分结束后的数组分为两组：

第一组：由一开始的left指针到最后面两个指针指向的同一个数

第二组：由最后面两个指针指向的同一个数到一开始的right指针。

（注：所以要用两个整数来存储原来传进来的左右指针（int left\_change = left; int right\_change = right;））

# 二、快速排序的时间复杂度和空间复杂度 #

本人不才，借鉴他人：http://blog.csdn.net/yuzhihui\_no1/article/details/44198701

# 三、快速排序的代码实现Java #

public class Kuaishu {
    	public static void main(String[] args){  
            int[] arr=new int[]{23,5,15,37,59,45,2,156,32,48}; 
            change(arr,0,arr.length-1);
            show(arr);
        }  
        public static void show(int[] arr){  //输出函数  
            for(int a: arr){  
                System.out.println(a);  
            }  
        }  
    	public static void change(int[] arr,int left,int right){
    		if(left >= right){
    			return;
    		}
    		int temp = arr[left];    //取值不是取指针
    		int left_change = left;
    		int right_change = right;
    		while(left_change < right_change){
    			while(left_change < right_change && arr[right_change]>=temp){
    				right_change--;
    			}
    			/*arr[left_change]=arr[right_change];*/
    			if(left_change < right_change &&arr[right_change]<temp){    //出错
    				arr[left_change]=arr[right_change];
    				left_change++;
    			}
    			while(left_change < right_change && arr[left_change]<=temp){
    				left_change++;
    			}
    			/*arr[right_change]=arr[left_change];	*/
    			if(left_change < right_change &&arr[left_change]>temp){    //要多个判断，否则指针会出现left>right
    				arr[right_change]=arr[left_change];	
    				right_change--;
    			}
    		}
    		arr[right_change]=temp;
    		change(arr,left,left_change-1);
    		change(arr,left_change+1,right);
    	}
    }

# 四、参考文章 #

http://blog.csdn.net/yuzhihui\_no1/article/details/44198701

[SouthEast]: /images/20220601/973718453f3249419f6c2978203dc955.png