算法-快速排序
简述
将排序数加入数组,寻找基数(一般数组第一个数),然后从数组两端向中间遍历(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)