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

Java
218
0
0
2024-01-22
现在用的比较多的单点登录技术是什么？
上一篇
Java对象的序列化和反序列化
下一篇

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


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 - : right;
    if (left < right) {
        partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex-);
        quickSort(arr, partitionIndex+, right);
    }
    return arr;
}

function partition(arr, left ,right) {     // 分区操作
    var pivot = left,                      // 设定基准值（pivot）
        index = pivot +;
    for (var i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            //虽然这里i可能会等于index，对自身没必要移动，但没必要加判断，因为加了判断，所有要移动的都要判断，从而带来更大的负担
            swap(arr, i, index);
            index++;
        }
    }
    swap(arr, pivot, index -);
    return index-;
}

function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

//第二种方法
function partition(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 quickSort(arr, low, high) {
  if (low < high) {
    let pivot = partition(arr, low, high);
    quickSort(arr, low, pivot - 1);
    quickSort(arr, pivot + 1, high);
  }
  return arr;
}

Python

 def quickSort(arr, left=None, right=None):
    left = if not  isinstance (left,(int, float)) else left
    right = len(arr)- if not isinstance(right,(int, float)) else right
    if left <  right :
        partitionIndex = partition(arr, left, right)
        quickSort(arr, left, partitionIndex-)
        quickSort(arr, partitionIndex+, right)
    return arr
def partition(arr, left, right):
    pivot = left
    index = pivot+
    i = index
    while  i <= right:
        if arr[i] < arr[pivot]:
            swap(arr, i, index)
            index+=
        i+=
    swap(arr,pivot,index-)
    return index-
def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

Go

 func quickSort(arr []int) []int {
    return _quickSort(arr,, len(arr)-1)
}
func _quickSort(arr []int, left, right int) []int {
    if left < right {
        partitionIndex := partition(arr, left, right)
        _quickSort(arr, left, partitionIndex-)
        _quickSort(arr, partitionIndex+, right)
    }
    return arr
}
func partition(arr []int, left, right int) int {
    pivot := left
    index := pivot +
    for i := index; i <= right; i++ {
        if arr[i] < arr[pivot] {
            swap(arr, i, index)
            index +=
        }
    }
    swap(arr, pivot, index-)
    return index -
}
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,, 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 -);
            quickSort(arr, partitionIndex +, right);
        }
        return arr;
    }
    private int partition(int[] arr, int left, int right) {
        // 设定基准值（pivot）
        int pivot = left;
        int index = pivot +;
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                swap(arr, i, index);
                index++;
            }
        }
        swap(arr, pivot, index -);
        return index -;
    }
    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) <=)
        return $arr;
    $middle = $arr[];
    $leftArray = array();
    $rightArray = array();
    for ($i =; $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];    // 第个元素作为基准数
        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-);  // 递归调用，将剩下两部分继续进行快排
        QuickSort(A, i+, end);
    }
}

C++

  // 严蔚敏 《数据结构》标准分割函数
 Paritition(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 = Paritition(A, low, high);
     QuickSort(A, low, pivot -);
     QuickSort(A, pivot +, 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 =; i < _nLength; i++)
     {
         _nArray[i] = Convert.ToInt(_sArray[i]);
     }

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

     foreach (var i in list)
     {
          Console.WriteLine(i.ToString());
     }
     while (true)
     {
         Thread.Sleep();
     }
}
 //获取按枢轴值左右分流后枢轴的位置
 private static int Division(List<int> list, int left, int right)
 {
     while (left < right)
     {
         int num = list[left]; //将首元素作为枢轴
         if (num > list[left +])
         {
             list[left] = list[left +];
             list[left +] = num;
             left++;
         }
         else
         {
             int temp = list[right];
             list[right] = list[left +];
             list[left +] = 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 +, right);
         //对枢轴的右边部分进行排序
         QuickSort(list, left, i -);
     }
 }

Ruby

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

#test
test_len =

random_array = []
test_len.times do
   random_array << rand()
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 -=
        }
        list[i] = list[j]
        while i < j , list[i] <= temp {
            i +=
        }
        list[j] = list[i]
    }
    let position = i
    list[position] = temp
    quickSort(&list, low: low, high: position -)
    quickSort(&list, low: position +, high: high)
}

Objective-C

 /**
 *  快速排序
 *
 *  @param list array
 */+(void)quickSort:(NSMutableArray *)list{
    if (list.count <=) {
        return;
    }
    [self quickSort:list startIndex: 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-];
    //对关键数据后面的数据进行快速排序
    [self quickSort:list startIndex:low+ endIndex:end];
}

Shell

 #!/bin/bash
function array()
{
  local a=(`echo "$@"`)
  local s=${a[${#a[@]}-]}
  local t=${a[${#a[@]}-]}
  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-]
       done
       mid=${arr[j]}
       arr[j]=${arr[i]}
       arr[i]=$mid
       while [[ "$i" -lt "$j" && "${arr[i]}" -le "$temp" ]]
       do
         i=$[i+]
       done
       mid=${arr[j]}
       arr[j]=${arr[i]}
       arr[i]=$mid
    done
    arr[i]=$temp
    array arr[*] $s $[i-]
    array arr[*] $[i+] $t
   fi
}

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

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

现在用的比较多的单点登录技术是什么？
上一篇
Java对象的序列化和反序列化
下一篇