算法-快速排序

简述

将排序数加入数组，寻找基数（一般数组第一个数），然后从数组两端向中间遍历(i,j)，每一次遍历的数都和基数比较，如果从右边向左边遍历的数找到了一个小于基数的数就停下，从左往右的找到了一个比基数大的数就停下，然后将这两个数互换位置，然后继续遍历互换，直到i和j碰面在一个位置，然后将基数和i，j所在位置的数互换位置，再以换了位置的基数为分界线，得到数组左边数和右边数，将左边和右边分别作为一个整体继续像上面一样遍历互换，完成排序。

时间复杂度

O(NlogN)

Java

import java.util.Arrays;
import java.util.Scanner;
public class Ceshi {
    public void sort(int[]a,int left, int right){
        int i,j,t,temp;
        if (left > right){
            return;
        }
        i = left;
        j = right;
        temp = a[i];
        while (i!=j){
            //左边j先查找
            while (a[j]>=temp && i<j){
                j--;
            }
            //右边开始
            while (a[i]<=temp && i<j){
                i++;
            }
            if (i<j){
                t = a[i];
                a[i] =a[j];
                a[j] =t;
            }
        }
        a[left]=a[i];
        a[i] = temp;
        sort(a,left,j-1);
        sort(a,j+1,right);
    }
    public void Mains(){
        //最常用的排序---快速排序
        //创建数组存储要排序的数
        //输入排序数 得到排序数组
        int p = 15; //排序元素个数
        int[] nub = new int[p];
        for (int i = 1;i<=p;i++){
            System.out.println("请输入要排序的数：");
            Scanner scanner = new Scanner(System.in);
            if (scanner.hasNextInt()){
                nub[i-1] = scanner.nextInt();
            }
        }
        //开始排序
        sort(nub,0,p-1);
        //输出排序完后的数组
        System.out.println(Arrays.toString(nub));
    }
}

Python

# 快速排序
list = []
def sort(left, right):
    if left > right:
        return
    i = left
    j = right
    temp = list[i]
    while i != j:
        while temp <= list[j] and i < j:
            j -= 1
        while temp >= list[i] and i < j:
            i += 1
        if i < j:
            t = list[j]
            list[j] = list[i]
            list[i] = t
    list[left] = list[i]
    list[i] = temp
    sort(left, i - 1)
    sort(i + 1, right)
for i in range(5):
    list.append(int(input("请输入数字:")))
sort(0, len(list) - 1)
print(list)