您的位置 首页 java

12种语言实现快速排序，值得收藏

智云科技发布于 2023年8月11日评论关闭阅读(67)

前言：我将持续输出对你有用文章，欢迎关注！

12种语言实现快速排序，值得收藏

查尔斯·安东尼·理查德·霍尔爵士，昵称东尼·霍尔

快速排序 （Quick Sort）是由 图灵奖 得主东尼·霍尔（ Tony Hoare ）所提出的一种排序算法。在平均状况下，排序 n 个元素要 次比较。在最坏状况下则需要 次比较，但这种状况并不常见。

快速排序使用 分治法 （Divide and conquer）策略来把一个列表（list）分为两个子列表（sub-lists），然后递归地排序两个子列表。

“快速排序”只是一个名字而已，以后会有人取“最快排序”吗？不过，目前 快速排序算法 通常比其他 算法更快，原因请看 《哪种排序算法最快》。

JavaScript 语言实例
Python 语言实例
Go 语言实例
Java 语言实例
PHP 语言实例
C 语言实例
C++ 语言实例
C# 语言实例
Ruby 语言实例
Swift 语言实例
Objective-C 语言实例
Shell 语言实例

1. 算法步骤

  1. 挑选基准值 ：从数列中挑出一个元素（一般会挑选最左边的元素），称为 “基准”（pivot）;
  2. 分区 ：对该数列每个元素，比基准值小的放在基准前面，比基准值大的摆在基准的后面（相等的可以到任一边）。遍历完所有元素时，将基准（pivot）移至两个子数列之间。这个过程称为分区（ partition ）操作；
  3. 递归排序子数列 ：递归地（recursive）对第2步得到的两个子数列进行分区操作；

递归到最后，子数列元素为0个或1个，即这个子数列已经被排序好了，此时退出递归。

2. 动图演示

12种语言实现快速排序，值得收藏

快速排序动图演示

先看下面的颜色说明会更容易理解上面的动图：

黄色 为当前的基准值
橙色 为已排序好的元素
绿色 为比基准值小的元素
紫色 为比基准值大的元素
红色 表示当前正比较的元素
蓝色 表示待比较的元素

各语言实例

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]) {
            //虽然这里i可能会等于index，对自身没必要移动，但没必要加判断，因为加了判断，所有要移动的都要判断，从而带来更大的负担
            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 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]

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]
}

Java 

 public class QuickSort implements IArraySort {
    @ Override 
    public int[] sort(int[] sourceArray) throws  Exception  {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays. copy Of(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 

 // 基本双向快速排序
void QuickSort(int *A, int start, int end)
{
    if(start<end){                // 调试时少了这一步，一直报错
        int i=start, j=end;
        int pivot = A[i];    // 第0个元素作为基准数
        while(i<j)
        {
            while(i<j && A[j]>pivot) j--;
            A[i] = A[j];
            while(i<j && A[i]<pivot) i++;
            A[j] = A[i];
        }
        A[i] = pivot;          // 基准数归位，i左边为较小数，右边为较大数
        QuickSort(A, start, i-1);  // 递归调用，将剩下两部分继续进行快排
        QuickSort(A, i+1, end);
    }
}

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);
   }
 }

C# 

  static  void Main(string[] args)
 {
     Console. Write Line("请输入待排序数列(以","分割):");
     string _s = Console.ReadLine();
     string[] _sArray = _s.Split(",".ToCharArray());
     int _nLength = _sArray.Length;
     int[] _nArray = new int[_nLength];
     for (int i = 0; i < _nLength; i++)
     {
         _nArray[i] = Convert.ToInt32(_sArray[i]);
     }

     var list = _nArray.ToList();
     QuickSort(list, 0, _nLength - 1);

     foreach (var i in list)
     {
          Console.WriteLine(i.ToString());
     }
     while (true)
     {
         Thread.Sleep(10000);
     }
}
 //获取按枢轴值左右分流后枢轴的位置
 private static int Division(List<int> list, int left, int right)
 {
     while (left < right)
     {
         int num = list[left]; //将首元素作为枢轴
         if (num > list[left + 1])
         {
             list[left] = list[left + 1];
             list[left + 1] = num;
             left++;
         }
         else
         {
             int temp = list[right];
             list[right] = list[left + 1];
             list[left + 1] = temp;
             right--;
         }
         Console.WriteLine(string.Join(",", list));
     }
     Console.WriteLine("--------------n");
     return left; //指向的此时枢轴的位置
 }
 private static void QuickSort(List<int> list, int left, int right)
 {
     if (left < right)
     {
         int i = Division(list, left, right);
         //对枢轴的左边部分进行排序
         QuickSort(list, i + 1, right);
         //对枢轴的右边部分进行排序
         QuickSort(list, left, i - 1);
     }
 }

Ruby 

 class Array
   def quick_sort
      return self if self.length<=1
      k = self[0]
      head = 0
       tail  = self.length - 1
      while head < tail
         (tail-head).times do
            if self[tail] < k
               self[tail], self[head] = self[head], self[tail]
               break
            end
            tail = tail - 1
         end
         (tail-head).times do
            if self[head] > k
               self[tail], self[head] = self[head], self[tail]
               break
            end
            head = head + 1
         end
      end
      [*(self.slice(0, head).quick_sort), self[head], *(self.slice(head+1, self.length-head-1).quick_sort)]
   end
end

#test
test_len = 20

random_array = []
test_len.times do
   random_array << rand(100)
end

puts "random_array            = [#{random_array.join(', ')}]"

puts "random_array.quick_sort = [#{random_array.quick_sort.join(', ')}]"
puts "random_array.sort       = [#{random_array.sort.join(', ')}]"
puts "quick_sort #{(random_array.quick_sort == random_array.sort) ? "succeed" : 'failed'}."

Swift 

     func quickSort(_ list : inout [Int], low : Int , high : Int){
        if low >= high{
            return
        }
        var i = low,j = high
        let temp = list[low]
        while i < j{
            while i < j , list[j] >= temp{
                j -= 1
            }
            list[i] = list[j]
            while i < j , list[i] <= temp {
                i += 1
            }
            list[j] = list[i]
        }
        let position = i
        list[position] = temp
        quickSort(&list, low: low, high: position - 1)
        quickSort(&list, low: position + 1, high: high)
    }

Objective-C 

 /**
 *  快速排序
 *
 *  @param list array
 */+(void)quickSort:(NSMutableArray *)list{
    if (list.count <= 1) {
        return;
    }
    [self quickSort:list startIndex:0 endIndex:list.count-1];
}

/**
 *  快速排序
 *  任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面
 *  再分别对两边的数据进行快速排序
 *  @param list  数组
 *  @param start 低位索引
 *  @param end   高位索引
 */+(void)quickSort:(NSMutableArray *)list startIndex:(NSInteger)start endIndex:(NSInteger)end{
    if (start >= end) { //低位大于高位，排序结束
        return;
    }
    NSInteger low = start;
    NSInteger high = end;
    NSInteger key = [[list objectAtIndex:start] integerValue]; //取第一个数作为关键数据
    while (low < high) {

        //从后往前推，直到找到第一个比关键数据小的值
        while ([[list objectAtIndex:high] integerValue] >= key && low < high) {
            high--;
        }
        //将这个值与关键数据对调（关键数据处于low位置），对调完关键数据处于high位置
        [list exchangeObjectAtIndex:low withObjectAtIndex:high];

        //从前往后推，直到找到第一个比关键数据大的值
        while ([[list objectAtIndex:low] integerValue] <= key && low < high) {
            low++;
        }
        //将这个值与关键数据（关键数据已经处于high位置）对调，对调完关键数据处于low位置
        [list exchangeObjectAtIndex:high withObjectAtIndex:low];
    }
    //对关键数据前面的数据进行快速排序
    [self quickSort:list startIndex:start endIndex:low-1];
    //对关键数据后面的数据进行快速排序
    [self quickSort:list startIndex:low+1 endIndex:end];
}

Shell 

 #!/bin/bash
function array()
{
  local a=(`echo "$@"`)
  local s=${a[${#a[@]}-2]}
  local t=${a[${#a[@]}-1]}
  if [ "$s" -lt "$t" ];
  then
    i=$s
    j=$t
    temp=${arr[s]}
    while [ "$i" -ne "$j" ]
    do
       while [[ "$j" -gt "$i" && "${arr[j]}" -ge "$temp" ]]
       do
         j=$[j-1]
       done
       mid=${arr[j]}
       arr[j]=${arr[i]}
       arr[i]=$mid
       while [[ "$i" -lt "$j" && "${arr[i]}" -le "$temp" ]]
       do
         i=$[i+1]
       done
       mid=${arr[j]}
       arr[j]=${arr[i]}
       arr[i]=$mid
    done
    arr[i]=$temp
    array arr[*] $s $[i-1]
    array arr[*] $[i+1] $t
   fi
}

arr=(13 12 16 14 15 333 3 24 9 14)
array arr[*] 0 9
echo ${arr[*]}

作者简介：茂子，热爱编程的家伙，欢迎关注。

标签:
打赏 点赞(2)

文章来源：智云一二三科技

文章标题：12种语言实现快速排序，值得收藏

文章地址：https://www.zhihuclub.com/189347.shtml

关于作者: 智云科技

相关文章

热门文章

1分享新浪图床上传接口源码

点赞(937)阅读(61,077)

2PHP简单实现路由Route功能

点赞(1.15K)阅读(35,960)

3Tideways、xhprof 和 xhgui 打造 PHP 非侵入式监控平台

点赞(363)阅读(4,286)

4centos系统如何查看是否安装了mysql

点赞(535)阅读(3,784)

5curl 工具简述

点赞(507)阅读(2,974)
网站地图