快速排序

Posted on by mannuan 2 mins read
Table of Contents

快速排序

过程描述

对数组的每一个部分，分别根据base进行元素的划分
在元素的划分过程中，需要借助两个指针i,j; 分别向后和向前移动

javascript实现

function partion(arr, left, right){
  let base = arr[left];
  let i = left;
  let j = right;
  while(i<j){
    while(arr[j]>=base&&i<j){
      j--;
    }
    while(arr[i]<=base&&i<j){
      i++;
    }
    let tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
  }
  arr[left] = arr[i];
  arr[i] = base;
  return i;
}
function quickSort(arr, left, right){
  if(left < right){
    let m = partion(arr, left, right);
    quickSort(arr, left, m);
    quickSort(arr, m+1,right);
  }
}

c++实现

  # include<iostream>
  # include<cstring>
  # include<cstdlib>
  using namespace std;

  int partion(int arr[], int left, int right){
      int base = arr[left];
      int i = left;
      int j = right;
      while(i<j){
          while(arr[j]>=base&&i<j){
              j--;
          }
          while(arr[i]<=base&&i<j){
              i++;
          }
          int tmp = arr[i];
          arr[i] = arr[j];
          arr[j] = tmp;
      }
      arr[left] = arr[i];
      arr[i] = base;
      return i;
  }

  void quickSort(int arr[], int left, int right){
      if(left < right){
          int m = partion(arr, left, right);
          quickSort(arr, left, m);
          quickSort(arr, m+1, right);
      }
  }

  int main(){
      const int n = 10;
      int arr[n] = {0};
      for(int i=0;i<n;i++){
          arr[i] = rand() % n + 0;
      }
      for(int i=0;i<n;i++){
          cout<< arr[i] << " ";
      }
      cout<<endl;
      quickSort(arr, 0, n);
      for(int i=0;i<n;i++){
          cout<< arr[i] << " ";
      }
      cout<<endl;
      return 0;
  }

python实现

import random
arr = [random.randint(0, 9) for i in range(10)]
def partion(arr, left, right):
  base = arr[left]
  i = left
  j = right
  while i < j:
    while arr[j] >= base and i < j:
      j-=1
    while arr[i]<=base and i < j:
      i+=1
    arr[i], arr[j] = arr[j], arr[i]
  arr[left] = arr[i]
  arr[i] = base
  return i

def quickSort(arr, left, right):
  if left < right:
    m = partion(arr, left, right)
    quickSort(arr, left, m)
    quickSort(arr, m+1, right)
print(arr)
quickSort(arr, 0, len(arr) -1)
print(arr)