更多精彩内容,欢迎关注:

视频号
视频号

抖音
抖音

快手
快手

微博
微博

快速排序c语言

文档

快速排序c语言

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较,但这种状况并不常见。事实上,快速排序通常明显比其他 Ο(nlogn) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。
推荐度:
导读快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较,但这种状况并不常见。事实上,快速排序通常明显比其他 Ο(nlogn) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。
.example-btn{color:#fff;background-color:#5cb85c;border-color:#4cae4c}.example-btn:hover{color:#fff;background-color:#47a447;border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%;color:#000;background-color:#f6f4f0;background-color:#d0e69c;background-color:#dcecb5;background-color:#e5eecc;margin:0 0 5px 0;padding:5px;border:1px solid #d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc 100px);background-image:linear-gradient(#fff,#e5eecc 100px)}div.example_code{line-height:1.4em;width:98%;background-color:#fff;padding:5px;border:1px solid #d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;word-break:break-all;word-wrap:break-word}div.example_result{background-color:#fff;padding:4px;border:1px solid #d4d4d4;width:98%}div.code{width:98%;border:1px solid #d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}div.code div{font-size:110%}div.code div,div.code p,div.example_code p{font-family:"courier new"}pre{margin:15px auto;font:12px/20px Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1px solid #ddd;border-left-width:4px;padding:10px 15px}

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

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较,但这种状况并不常见。事实上,快速排序通常明显比其他 Ο(nlogn) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。

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

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

快速排序的名字起的是简单粗暴,因为一听到这个名字你就知道它存在的意义,就是快,而且效率高!它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n?),但是人家就是优秀,在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好,可是这是为什么呢,我也不知道。好在我的强迫症又犯了,查了 N 多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案:

快速排序的最坏运行情况是 O(n?),比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn),且 O(nlogn) 记号中隐含的常数因子很小,比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以,对绝大多数顺序性较弱的随机数列而言,快速排序总是优于归并排序。

1. 算法步骤

从数列中挑出一个元素,称为 "基准"(pivot);

重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;

递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序;

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;}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 arrdef 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-1def swap(arr, i, j):    arr[i], arr[j] = arr[j], arr[i]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]}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);   } }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;    }}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);}C实例 typedef struct _Range {    int start, end;} Range;Range new_Range(int s, int e) {    Range r;    r.start = s;    r.end = e;    return r;}void swap(int *x, int *y) {    int t = *x;    *x = *y;    *y = t;}void quick_sort(int arr[], const int len) {    if (len <= 0)        return; // 避免len等於負值時引發段錯誤(Segment Fault)    // r[]模擬列表,p為數量,r[p++]為push,r[--p]為pop且取得元素    Range r[len];    int p = 0;    r[p++] = new_Range(0, len - 1);    while (p) {        Range range = r[--p];        if (range.start >= range.end)            continue;        int mid = arr[(range.start + range.end) / 2]; // 選取中間點為基準點        int left = range.start, right = range.end;        do {            while (arr[left] < mid) ++left;   // 檢測基準點左側是否符合要求            while (arr[right] > mid) --right; //檢測基準點右側是否符合要求            if (left <= right) {                swap(&arr[left], &arr[right]);                left++;                right--;               // 移動指針以繼續            }        } while (left <= right);        if (range.start < right) r[p++] = new_Range(range.start, right);        if (range.end > left) r[p++] = new_Range(left, range.end);    }}

递归法

实例 void swap(int *x, int *y) {    int t = *x;    *x = *y;    *y = t;}void quick_sort_recursive(int arr[], int start, int end) {    if (start >= end)        return;    int mid = arr[end];    int left = start, right = end - 1;    while (left < right) {        while (arr[left] < mid && left < right)            left++;        while (arr[right] >= mid && left < right)            right--;        swap(&arr[left], &arr[right]);    }    if (arr[left] >= arr[end])        swap(&arr[left], &arr[end]);    else        left++;    if (left)        quick_sort_recursive(arr, start, left - 1);    quick_sort_recursive(arr, left + 1, end);}void quick_sort(int arr[], int len) {    quick_sort_recursive(arr, 0, len - 1);}C++

函数法

sort(a,a + n);// 排序a[0]-a[n-1]的所有数.

迭代法

实例 // 参考:http://www.dutor.net/index.php/2011/04/recursive-iterative-quick-sort/struct Range {    int start, end;    Range(int s = 0, int e = 0) {        start = s, end = e;    }};template // 整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)、"大於"(>)、"不小於"(>=)的運算子功能void quick_sort(T arr[], const int len) {    if (len <= 0)        return; // 避免len等於負值時宣告堆疊陣列當機    // r[]模擬堆疊,p為數量,r[p++]為push,r[--p]為pop且取得元素    Range r[len];    int p = 0;    r[p++] = Range(0, len - 1);    while (p) {        Range range = r[--p];        if (range.start >= range.end)            continue;        T mid = arr[range.end];        int left = range.start, right = range.end - 1;        while (left < right) {            while (arr[left] < mid && left < right) left++;            while (arr[right] >= mid && left < right) right--;            std::swap(arr[left], arr[right]);        }        if (arr[left] >= arr[range.end])            std::swap(arr[left], arr[range.end]);        else            left++;        r[p++] = Range(range.start, left - 1);        r[p++] = Range(left + 1, range.end);    }}

递归法

实例 template void quick_sort_recursive(T arr[], int start, int end) {    if (start >= end)        return;    T mid = arr[end];    int left = start, right = end - 1;    while (left < right) { //在整个范围内搜寻比枢纽元值小或大的元素,然后将左侧元素与右侧元素交换        while (arr[left] < mid && left < right) //试图在左侧找到一个比枢纽元更大的元素            left++;        while (arr[right] >= mid && left < right) //试图在右侧找到一个比枢纽元更小的元素            right--;        std::swap(arr[left], arr[right]); //交换元素    }    if (arr[left] >= arr[end])        std::swap(arr[left], arr[end]);    else        left++;    quick_sort_recursive(arr, start, left - 1);    quick_sort_recursive(arr, left + 1, end);}template //整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)、"大於"(>)、"不小於"(>=)的運算子功能void quick_sort(T arr[], int len) {    quick_sort_recursive(arr, 0, len - 1);}

参考地址:

https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/6.quickSort.md

https://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F

以下是热心网友对快速排序算法的补充,仅供参考:

热心网友提供的补充1:

上方没有C#实现,我补充一下,如下所示:

//快速排序(目标数组,数组的起始位置,数组的终止位置)
static void QuickSort(int[] array, int left = 0, int right = -1)
{
    if (right.Equals(-1)) right = array.Length - 1;
    try
    {
        int keyValuePosition;   //记录关键值的下标
        //当传递的目标数组含有两个以上的元素时,进行递归调用。(即:当传递的目标数组只含有一个元素时,此趟排序结束)
        if (left < right)
        {
            keyValuePosition = Partion(array, left, right);  //获取关键值的下标(快排的核心)
            QuickSort(array, left, keyValuePosition - 1);    //递归调用,快排划分出来的左区间
            QuickSort(array, keyValuePosition + 1, right);   //递归调用,快排划分出来的右区间
        }
    }
    catch (Exception ex)
    {
        Console.WriteLine("Exception: {0}", ex);
    }
}

///快速排序的核心部分:确定关键值在数组中的位置,以此将数组划分成左右两区间,关键值游离在外。(返回关键值应在数组中的下标)
static int Partion(int[] array, int left, int right)
{
    int leftIndex = left;        //记录目标数组的起始位置(后续动态的左侧下标)
    int rightIndex = right;      //记录目标数组的结束位置(后续动态的右侧下标)
    int keyValue = array[left];  //数组的第一个元素作为关键值
    int temp;
    //当 (左侧动态下标 == 右侧动态下标) 时跳出循环
    while (leftIndex < rightIndex)
    {
        while (leftIndex < rightIndex && array[leftIndex] <= keyValue)  //左侧动态下标逐渐增加,直至找到大于keyValue的下标
        {
            leftIndex++;
        }
        while (leftIndex < rightIndex && array[rightIndex] > keyValue)  //右侧动态下标逐渐减小,直至找到小于或等于keyValue的下标
        {
            rightIndex--;
        }
        if (leftIndex < rightIndex)  //如果leftIndex < rightIndex,则交换左右动态下标所指定的值;当leftIndex==rightIndex时,跳出整个循环
        {
            temp = array[leftIndex];
            array[leftIndex] = array[rightIndex];
            array[rightIndex] = temp;
        }
    }

    //当左右两个动态下标相等时(即:左右下标指向同一个位置),此时便可以确定keyValue的准确位置
    temp = keyValue;
    if (temp < array[rightIndex])   //当keyValue < 左右下标同时指向的值,将keyValue与rightIndex - 1指向的值交换,并返回rightIndex - 1
    {
        array[left] = array[rightIndex - 1];
        array[rightIndex - 1] = temp;
        return rightIndex - 1;
    }
    else //当keyValue >= 左右下标同时指向的值,将keyValue与rightIndex指向的值交换,并返回rightIndex
    {
        array[left] = array[rightIndex];
        array[rightIndex] = temp;
        return rightIndex;
    }
}

热心网友提供的补充2:

补充 scala 实现版本:

/**  
* @Auther: huowang 
* @Date: 19:34:47 2020/12/10  
* @DES:  分区交换算法(快速排序发)  
* @Modified By:  
*/
object PartitionExchange {

  /**    
   * 分区内切割    
   * @param arr    
   * @param left    
   * @param right    
   * @return    
  */  
def partition(arr:Array[Int],left:Int,right: Int):Int={
    // 获取基准元素 直接选取最右侧一个元素为基准元素   
    val pv=arr(right)

    // 把最左边一个索引作为堆叠索引   
     var storeIndex=left
    //操作数组 -1是因为 最右边一个元素是基准元素  
   for (i <- left to right-1 ){
       if(arr(i)<=pv){
         //把小于基准元素的元素 都堆到集合左端        
          swap(arr,storeIndex,i)
         // 把用于堆叠索引往前移动一个  
          storeIndex=storeIndex+1 
      }
      //如果出现了比基准元素大的元素,那么则不会移动堆叠索引  
      // 但是如果之后又出现了比基准元素小的元素,那边会与这个大的元素交换位置
      // 进而使大的元素永远出现在堆叠索引右侧
    }
    // 这里最有右的元素,其实是基准元素,我们把基准元素和最后堆叠索引对应的元素调换位置
    // 这样基准元素左边就都是大于它的元素了  
     swap(arr,right,storeIndex)
    // 返回堆叠索引位置,目前堆叠索引指向的就是基准元素 
     storeIndex
  }

def quicksort(arr:Array[Int],left: Int,right: Int):Array[Int]={

    if(right>left){
      // 左右索引不重合 
     // 随便选择一个元素作为基准 就选择最左边的吧 
     var pivotIndex=0 
     // 切割返回基准元素 
     pivotIndex= partition(arr,left,right)
      // 递归对切割形成的两个子集进行排序 
      quicksort(arr,left,pivotIndex-1)
      quicksort(arr,pivotIndex,right)
    }
    arr
  }


  /**    
    * 调换 a b 元素在数组中的位置    
    * @param arr    
    * @param a    
    * @param b    
    */  
def swap(arr:Array[Int],a:Int,b:Int)={
    val tmp=arr(a)
    arr(a)=arr(b)
    arr(b)=tmp
  }

def main(args: Array[String]): Unit = {
    // 测试
    val arr=Array(5, 2, 9,11,3,6,8,4,0,0)
    val arrNew=quicksort(arr,0,arr.size-1)
    println(arrNew.toList.mkString(","))

  }
}

热心网友提供的补充3:

补充一下迭代法的 python 实现:

def _partition(array:list, start:int, end:int) -> int:
    """
    将数组指定片段进行左右划分,首先选择中位元素为中值。

    比中位元素小的置于其左,与中位元素相等或比中位元素大的置于其右,

    最后返回中位元素的下标位置。
    """
    # 以中位元素为中值划分,尽量避免极端情况
    mid = (start + end) >> 1
    array[start], array[mid] = array[mid], array[start]
    
    # 划分的实现
    i, j = start, end
    x = array[start]
    while (i < j):
        if (i < j and array[j] >= x): j -= 1
        array[i] = array[j]
        if (i < j and array[i] < x): i += 1
        array[j] = array[i]
    array[i] = x

    return i


def quickSort(array:list) -> list:
    """
    迭代法快速排序,队列结构辅助实现。
    """
    sorted_array = array.copy()
    length = len(sorted_array)
    # 使用队列保存每次划分的二元组:(起始下标,终止下标)
    queue = []
    queue.append((0, length - 1))

    # 队列为空,则所有划分操作执行完毕
    while len(queue):
        left, right = queue.pop(0)
        pos = _partition(sorted_array, left, right)
        # 默认长度为 1 的序列有序,那么区间长度 > 1 才需要划分,才需要保存到队列中
        if (left < pos - 1): queue.append((left, pos - 1))
        if (pos + 1 < right): queue.append((pos + 1, right))
    
    return sorted_array


if __name__ == "__main__":
    array = [21, -17, 1, -27, 41, 17, -5, -49]
    sorted_array = quickSort(array)
    print("排序前:{array1}
排序后:{array2}".format(array1=array, array2=sorted_array))
以上为快速排序算法详细介绍,插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等排序算法各有优缺点,用一张图概括:

关于时间复杂度

平方阶 (O(n2)) 排序 各类简单排序:直接插入、直接选择和冒泡排序。

线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序;

O(n1+§)) 排序,§ 是介于 0 和 1 之间的常数。 希尔排序

线性阶 (O(n)) 排序 基数排序,此外还有桶、箱排序。

关于稳定性

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

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

名词解释:

n:数据规模

k:"桶"的个数

In-place:占用常数内存,不占用额外内存

Out-place:占用额外内存

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

文档

快速排序c语言

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较,但这种状况并不常见。事实上,快速排序通常明显比其他 Ο(nlogn) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。
推荐度:
为你推荐
资讯专栏
热门视频
相关推荐
两句关于动物的诗句 踏青的诗词名句 含有燕子的诗句 简述归并排序算法的基本思路 希尔排序怎么排 直接选择排序 基数排序流程图 python冒泡排序算法 桶排序c语言 计数排序菜鸟教程 堆排序算法规则 描写兰花的诗句古诗 快速排序算法java 带有动物的古诗 关于踏青的唯美诗句 关于描写燕子的诗句 归并排序算法python思想 希尔排序实现 直接选择排序稳定吗 基数排序算法代码 关于兰花的诗句古诗 堆排序法排序怎么排 计数排序算法c++实现 桶式排序 关于放风筝的古诗 冒泡排序python 基数排序怎么排 选择排序法 希尔排序 归并排序python 描写燕子的古诗绝句 踏青诗句最出名诗句 描写夏天的诗句简单 关于写小动物的诗 java快速排序 关于兰花的诗句两句 堆排序怎么排 描写元宵节的唯美诗词 如何按照计数进行排序 桶排序
Top