十大经典排序算法——快速排序 （Java、JavaScript、PHP、Python、Go语言实现，javascriptpython

十大经典排序算法之——快速排序

本文主要介绍十大经典排序算法中的“快速排序”，并附上快速排序算法的Java、JavaScript、PHP、Python、Go语言实现。

1、十大经典排序算法介绍

排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。

2、十大经典排序算法比较

注：关于时间复杂度

1.平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。
2.线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序。
3.O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。希尔排序。
4.线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。

注：关于稳定性

稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。

相关名词解释：n：数据规模，k：“桶”的个数，In-place：占用常数内存，不占用额外内存，Out-place：占用额外内存。

3、细说快速排序

3.1 快速排序介绍

在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。快速排序通常明显比其他 Ο(nlogn) 算法更快。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

3.2 快速排序算法步骤

1.从数列中挑出一个元素，称为 “基准”（pivot）;
2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

3.3 快速排序动画演示

3.4 快速排序算法的代码实现

3.4.1 Java实现

public class QuickSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        return quickSort(arr, 0, arr.length - 1);
    }

    private int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int partitionIndex = partition(arr, left, right);
            quickSort(arr, left, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, right);
        }
        return arr;
    }

    private int partition(int[] arr, int left, int right) {
        // 设定基准值（pivot）
        int pivot = left;
        int index = pivot + 1;
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                swap(arr, i, index);
                index++;
            }
        }
        swap(arr, pivot, index - 1);
        return index - 1;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}

3.4.2 JavaScript实现

function quickSort(arr, left, right) {
   var len = arr.length,
       partitionIndex,
       left = typeof left != 'number' ? 0 : left,
       right = typeof right != 'number' ? len - 1 : right;

   if (left < right) {
       partitionIndex = partition(arr, left, right);
       quickSort(arr, left, partitionIndex-1);
       quickSort(arr, partitionIndex+1, right);
   }
   return arr;
}

function partition(arr, left ,right) {     // 分区操作
   var pivot = left,                      // 设定基准值（pivot）
       index = pivot + 1;
   for (var i = index; i <= right; i++) {
       if (arr[i] < arr[pivot]) {
           swap(arr, i, index);
           index++;
       }        
   }
   swap(arr, pivot, index - 1);
   return index-1;
}

function swap(arr, i, j) {
   var temp = arr[i];
   arr[i] = arr[j];
   arr[j] = temp;
}
function partition2(arr, low, high) {
 let pivot = arr[low];
 while (low < high) {
   while (low < high && arr[high] > pivot) {
     --high;
   }
   arr[low] = arr[high];
   while (low < high && arr[low] <= pivot) {
     ++low;
   }
   arr[high] = arr[low];
 }
 arr[low] = pivot;
 return low;
}

function quickSort2(arr, low, high) {
 if (low < high) {
   let pivot = partition2(arr, low, high);
   quickSort2(arr, low, pivot - 1);
   quickSort2(arr, pivot + 1, high);
 }
 return arr;
}

3.4.3 PHP实现

function quickSort($arr)
{
    if (count($arr) <= 1)
        return $arr;
    $middle = $arr[0];
    $leftArray = array();
    $rightArray = array();

    for ($i = 1; $i < count($arr); $i++) {
        if ($arr[$i] > $middle)
            $rightArray[] = $arr[$i];
        else
            $leftArray[] = $arr[$i];
    }
    $leftArray = quickSort($leftArray);
    $leftArray[] = $middle;

    $rightArray = quickSort($rightArray);
    return array_merge($leftArray, $rightArray);
}

3.4.4 Python实现

def quickSort(arr, left=None, right=None):
    left = 0 if not isinstance(left,(int, float)) else left
    right = len(arr)-1 if not isinstance(right,(int, float)) else right
    if left < right:
        partitionIndex = partition(arr, left, right)
        quickSort(arr, left, partitionIndex-1)
        quickSort(arr, partitionIndex+1, right)
    return arr

def partition(arr, left, right):
    pivot = left
    index = pivot+1
    i = index
    while  i <= right:
        if arr[i] < arr[pivot]:
            swap(arr, i, index)
            index+=1
        i+=1
    swap(arr,pivot,index-1)
    return index-1

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

3.4.5 Go语言实现

func quickSort(arr []int) []int {
	return _quickSort(arr, 0, len(arr)-1)
}

func _quickSort(arr []int, left, right int) []int {
	if left < right {
		partitionIndex := partition(arr, left, right)
		_quickSort(arr, left, partitionIndex-1)
		_quickSort(arr, partitionIndex+1, right)
	}
	return arr
}

func partition(arr []int, left, right int) int {
	pivot := left
	index := pivot + 1

	for i := index; i <= right; i++ {
		if arr[i] < arr[pivot] {
			swap(arr, i, index)
			index += 1
		}
	}
	swap(arr, pivot, index-1)
	return index - 1
}

func swap(arr []int, i, j int) {
	arr[i], arr[j] = arr[j], arr[i]
}

3.4.6 C++实现

Paritition1(int A[], int low, int high) {
   int pivot = A[low];
   while (low < high) {
     while (low < high && A[high] >= pivot) {
       --high;
     }
     A[low] = A[high];
     while (low < high && A[low] <= pivot) {
       ++low;
     }
     A[high] = A[low];
   }
   A[low] = pivot;
   return low;
 }

 void QuickSort(int A[], int low, int high) //快排母函数
 {
   if (low < high) {
     int pivot = Paritition1(A, low, high);
     QuickSort(A, low, pivot - 1);
     QuickSort(A, pivot + 1, high);
   }
 }

4、快速排序总结

快速排序：选“基准”，“基准”大小两边排，迭代排序，是不稳定的排序算法。

5、其他排序算法

这里给出十大经典排序算法中的其他排序算法文章链接供参考、学习
冒泡排序：https://blog.csdn.net/weixin_43876206/article/details/89488568
选择排序：https://blog.csdn.net/weixin_43876206/article/details/89488999
插入排序：https://blog.csdn.net/weixin_43876206/article/details/89489021
归并排序：https://blog.csdn.net/weixin_43876206/article/details/89501450
希尔排序：https://blog.csdn.net/weixin_43876206/article/details/89490445

如有问题、想法，欢迎在此博客下面留言讨论