| 排序算法名称 | 针对的应用情景 |
|---|---|
| 快速排序 | 无序素组(对于基本有序数组和大量重复键值的数组复杂度上升至O(n2) |
| 随机速排 | 快速排序的优化,解决普通快排在部分有序数组中进行排序,每次取得的都是趋近最值 |
| 二路快排 | 随机速排的优化,解决数组中存在大量键值重复的情况以及基本有序数组 |
| 三路快排 | 二路排序的优化，把等于value的元素放在另一个区间内，不参与下次的排序。 |
从上到下都是基于上面的排序算法进行优化
swap方法原型
/**
* 没有办法想C语言的指针那样直接通过指针交换,可以通过数组或者是对象属性来交换
* @param arr 数组名
* @param x 下标
* @param y 下标
*/
public static void swap(int[] arr, int x, int y){
int temp;
temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
Java快速排序
ackage sort;
import org.junit.Test;
import static sort.PublicMethod.swap;
/**
* @author panghu
* @title: QuickSort
* @projectName Algorithm_And_Data_Structure
* @date 19-6-5 下午8:05
*/
public class QuickSort {
private void quickSort(int[] arr, int l, int r) {
if (l >= r){
return;
}
int position = partition(arr,l,r);
quickSort(arr,l,position-1);
quickSort(arr,position+1,r);
}
/*
* 对arr[l...r]部分进行partition操作
* 返回position,是的arr[l...p-1]<arr[p],arr[p+1...r]>arr[p]
* */
public static int partition(int[] arr,int left,int right){
int value = arr[left];
int position = left;
//这里的right值是最右边的值 arr[right]是有效的
for (int i=left+1;i<=right;i++){
if (arr[i] < value){
/*
* 相关的操作
* 1.比初始位置大的数都放在初始位置的右边一个,放一个position的位置增加一
* */
swap(arr,i,++position);
}
}
//走到这一步的时候 arr[l]存放的是分解值,arr[position]存放的是小于分界值
swap(arr,left,position);
return position;
}
@Test
public void test(){
int[] a = { 49, 38, 65, 97, 76, 13, 27, 50 };
quickSort(a, 0,a.length-1);
System.err.println("排好序的数组：");
for (int e : a) {
System.out.print(e+" ");
}
}
}
快速排序算法
思路:
- 从序列中挑选出一个元素(一般是第一个或者是最后一个)作为"基准"元素
- 把序列分成2个部分，其数值大于"基准"元素的元素放在"基准"元素的左边，否在放在"基准"元
素的右边，此时"基准"元素所在的位置就是正确的排序位置，这个过程被称为 partition（分区） - 递归将"基准"元素左边的序列和"基准"元素右边的序列进行partition操作
缺点:
- 当partition操作时,如果每次取得的的第一个元素趋近于最值,使得分治的任务极度不平衡,情况最坏时,快速排序算法的复杂度将上升到O(n2)**
- 存在大量重复键值时,同样会出现分治任务很不平衡的情况
随机快速排序算法
package sort;
import org.junit.Test;
import static sort.PublicMethod.swap;
/**
* @author panghu
* @title: RandomQuickSort
* @projectName Algorithm_And_Data_Structure
* @date 19-7-21 下午9:49
*/
public class RandomQuickSort {
private void quickSort(int[] arr, int l, int r) {
if (l >= r){
return;
}
int position = partition(arr,l,r);
quickSort(arr,l,position-1);
quickSort(arr,position+1,r);
}
/*
* 对arr[l...r]部分进行partition操作
* 返回position,是的arr[l...p-1]<arr[p],arr[p+1...r]>arr[p]
* */
public static int partition(int[] arr,int left,int right){
int value = arr[left];
//这个地方是唯一的区别.在left~right之间生成一个随机数
int ranNum = left + (int)(Math.random()*(right-left+1));
//把随机数作为索引,将索引对应值与最后一位值 right 交换
swap(arr,right,ranNum);
int position = left;
//这里的right值是最右边的值 arr[right]是有效的
for (int i=left+1;i<=right;i++){
if (arr[i] < value){
/*
* 相关的操作
* 1.比初始位置大的数都放在初始位置的右边一个,放一个position的位置增加一
* */
swap(arr,i,++position);
}
}
//走到这一步的时候 arr[l]存放的是分解值,arr[position]存放的是小于分界值
//自我感觉这一步 有一种一举两得,即将分界值的位置移到了正确位置,也将左值放在了左边
swap(arr,left,position);
return position;
}
@Test
public void test(){
int[] a = { 49, 38, 65, 97, 76, 13, 27, 50 };
quickSort(a, 0,a.length-1);
System.err.println("排好序的数组：");
for (int e : a) {
System.out.print(e+" ");
}
}
}
思路:
- 在每次partition的过程中,
将left到right-1之间的随机选取一个元素,与right进行位置交换,这样就解决了快排中如果数组部分有序,数组划分不平衡的情况
缺点
- 当数组中存在大量重复键值的时候任然会出现算法复杂度上升的情况
两路快速排序算法
package sort;
import org.junit.Test;
import static sort.PublicMethod.swap;
/**
* @author panghu
* @title: QuickSort2
* @projectName Algorithm_And_Data_Structure
* @date 19-7-22 下午10:27
*/
public class QuickSort2 {
private void quickSort(int[] arr, int l, int r) {
if (l >= r){
return;
}
int position = partition(arr,l,r);
quickSort(arr,l,position-1);
quickSort(arr,position+1,r);
}
int partition(int[] arr, int left, int right){
int ranNum = left + (int)(Math.random()*(right-left+1));
//把随机数作为索引,将索引对应值与最后一位值 right 交换
swap(arr,right,ranNum);
// arr[left+1...i) <= v; arr(j...right] >= v
int value = arr[left];
int i = left+1, j = right;
while( true ){
while( i <= right && arr[i] < value) {
i ++;
}
while( j >= left+1 && arr[j] > value ) {
j --;
}
if( i > j ) {
break;
}
swap(arr,i,j);
i ++;
j --;
}
swap(arr, left, j);
return j;
}
@Test
public void test(){
int[] a = { 49, 38, 65, 97, 76, 13, 27, 50 };
quickSort(a, 0,a.length-1);
System.err.println("排好序的数组：");
for (int e : a) {
System.out.print(e+" ");
}
}
}
二路快速排序
二路快速排序
思路:
- 从左边和右边分别遍历,当左边遍历到第i位置时,所对应的元素大于v,从右边遍历的元素遍历到第j个位置时,所对应的元素arr[j]<v,交换i和j的位置直到i>j.适用于有大量重复键值的情形和数组基本有序的问题
package sort;
import org.junit.Test;
import static sort.PublicMethod.swap;
/**
* @author panghu
* @title: QuickSort3
* @projectName Algorithm_And_Data_Structure
* @date 19-7-23 下午2:02
*/
public class QuickSort3 {
private void quickSort(int[] arr, int l, int r) {
if (l >= r){
return;
}
int position = partition(arr,l,r);
quickSort(arr,l,position-1);
quickSort(arr,position+1,r);
}
int partition(int[] arr,int left,int right){
int ranNum = left + (int)(Math.random()*(right-left+1));
//把随机数作为索引,将索引对应值与最后一位值 right 交换
swap(arr,right,ranNum);
// arr[left+1...i) <= value; arr(j...right] >= value
int value = arr[left];
// 将<v的分界线的索引值lt初始化为第一个元素的位置（也就是<v部分的最后一个元素所在位置）
int lt = left;
//将>value的分界线的索引值gt初始化为最后一个元素right的后一个元素所在位置
// （也就是>value部分的第一个元素所在位置）
int gt = right+1;
// 将遍历序列的索引值i初始化为 left+1
int i = left+1;
while (i < gt){
if (arr[i] < value){
swap(arr, lt+1, i);
//移动指针
i++;
//增加<value的部分
lt++;
}else if ( arr[i] > value){
swap(arr,gt-1,i);
//增加>value的部分
gt--;
//注意,这里不需要移动i,之前移动i是因为需要增加<value的部分
//而保持=i部分不懂,所以i和lt都需要移动
}else{
//增加=v的部分
i++;
}
}
return i;
}
@Test
public void test(){
int[] a = { 49, 38, 65, 97, 76, 13, 27, 50 };
quickSort(a, 0,a.length-1);
System.err.println("排好序的数组：");
for (int e : a) {
System.out.print(e+" ");
}
}
}
三路快速排序算法
三路快速排序算法
三路快速排序算法
三路快速排序算法
三路快速排序算法
思路:
- 之前的快速排序是将数组划分为 分成<=v和>v或者是<v和>=v的两个部分,而三路快排是将数组划分为分成三个部分:`<v、=v、>v
应用演示
package leetcode;
/**
* 题目要求：给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，
* 使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
* 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
*/
import java.util.Arrays;
/**
* @author panghu
* @title: Solution75
* @projectName Algorithm_And_Data_Structure
* @date 19-7-16 下午10:06
*/
public class Solution75 {
**
* 三路快速排序法的应用
* @param nums 传入的数组
*/
static void sortColors(int[] nums){
// nums[0...zero] == 0
int zero = -1;
// nums[two..n-1] == 2
int two = nums.length;
for (int i = 0;i < two;){
if (nums[i] == 1){
i++;
}else if (nums[i] == 2){
two--;
swap(nums,i,two);
}else {
if (nums[i] != 0){
throw new IllegalArgumentException("数组中的值只能为1,2,3");
}
zero++;
swap(nums,i,zero);
}
}
}
/**
* 通过数组交换数值
* @param arr 数组
* @param x 数组索引1
* @param y 数组索引2
*/
static void swap(int[] arr,int x,int y){
//temp用来临时存储值
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
public static void main(String[] args) {
int[] arr = {1,2,1,2,1,0,0,0,0,0};
sortColors(arr);
System.out.println(Arrays.toString(arr));
}
}
参考博客:https://www.cnblogs.com/deng-tao/p
参考课程:https://coding.imooc.com/class/chapter/71.html#Anchor
