时间戳

首页 > 技术文章 > 经典排序算法总结

经典排序算法总结

ronnieyuan 2019-11-21 14:56 原文

概述

  • 选泡插, 快归堆希桶计基, n方n老(log)n一三, 对n加kn乘k, 不稳稳稳不稳稳, 不稳不稳稳稳稳。

    排序算法 平均时间复杂度 最好情况 最坏情况 空间复杂度 排序方式 稳定性
    冒泡排序(BubbleSort) O(n2) O(n) O(n2) O(1) In-place 稳定
    选择排序(SelectSort) O(n2) O(n2) O(n2) O(1) In-place 不稳
    插入排序(InsertSort) O(n2) O(n) O(n2) O(1) In-place 稳定
    希尔排序(ShellSort) O(n1.3) O(n) O(n log2 n) O(1) In-place 不稳
    归并排序(MergeSort) O(n log n) O(n log n) O(n log n) O(n) Out-place 稳定
    快速排序(QuickSort) O(n log n) O(n log n) O(n2) O(log n) In-place 不稳
    堆排序(HeapSort) O(n log n) O(n log n) O(n log n) O(1) In-place 不稳
    计数排序(CountSort) O(n + k) O(n + k) O(n + k) O(k) Out-place 稳定
    桶排序(BucketSort) O(n + k) O(n + k) O(n2) O(n + k) Out-place 稳定
    基数排序(RadixSort) O(n x k) O(n x k) O(n x k) O(n + k) Out-place 稳定
    • 名词:
      • n: 数据规模
      • k: ’桶‘ 的个数
      • In-place: 占用常数内存, 不占用额外内存
      • Out-place: 占用额外内存
      • 稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同
    • 基于时间复杂度
      • O(n2) 排序: 各类简单排序: 直接插入, 直接选择 和冒泡排序。
      • O(n log n) 排序: 快速排序、堆排序 和 归并排序
      • O(n1+§)) 排序: 希尔排序
      • 线性阶 (O(n)) 排序: 基数排序, 桶排序
    • 基于稳定性
      • 稳定的排序算法: 冒泡, 插入, 归并 和基数
      • 不稳定的排序算法: 选择, 快速, 希尔, 堆

冒泡排序

  • Java 实现:

    public class BubbleSort {

    private static int[] sort(int[] arr){
        for (int i = 0; i < arr.length - 1; i++){
            for (int j = 0; j < arr.length - i - 1; j++){
                if (arr[j] > arr[j + 1]){
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        return arr;
    }

    private static void print(int[] arr){
        for(int i : arr){
            System.out.print(i + " ");
        }
    }

    public static void main(String[] args) {
        int[] arr01 = {3, 1, 5, 4, 9, 7, 6};
        int[] result = sort(arr01);
        print(result);
    }
}

  • Python 实现:

    def bubbleSort(arr):
	for i in range(len(arr) - 1):
		for j in range(len(arr) - i -1):
			if arr[j] > arr[j+1]:
				arr[j], arr[j+1] = arr[j+1], arr[j]

arr = [3, 1, 4, 8, 6]

bubbleSort(arr)
print(arr)

  • Golang 实现:

    package main

import "fmt"

func main()  {
	var arr = []int{3, 4, 1, 7, 5, 9}
	var arr2 = bubbleSort(arr)
	fmt.Println(arr2)
}

func bubbleSort(arr1 []int) (arr2 []int) {
	var i,j int
	for i = 0; i < len(arr1) - 1; i++{
		for j = 0; j < len(arr1) - i -1; j++ {
			if arr1[j] > arr1[j+1] {
				arr1[j], arr1[j+1] = arr1[j+1], arr1[j]
			}
			}
		}
	return arr1
}

  • Scala 实现:

    package com.ronnie.scala

object BubbleSort {
  def sort(array: Array[Int]): Array[Int] = {
    // if 可以加在for循环中
    for (i <- 0 until(array.length - 1); j <- 0 until(array.length - i - 1); if (array(j) > array(j + 1))) {
      val temp = array(j)
      array(j) = array(j + 1)
      array(j + 1) = temp
    }
    array
  }

  def main(args: Array[String]): Unit = {
    val arr01 = Array[Int](3, 1, 2, 7, 4, 6)
    val result = sort(arr01)
    printArray(result)
  }

  def printArray(array: Array[Int]): Unit = {
    array.foreach(println)
  }
}

选择排序

  • Java实现:

    package com.ronnie.algorithm.sort;

  public class SelectSort {

      private static int[] sort(int[] arr){
          int min = 0;
          for (int i = 0; i < arr.length - 1; i++){
              min = i;
              for (int j = i + 1; j < arr.length; j++){
                  if (arr[j] < arr[min]){
                      // 记录目前能找到的最小值元素下标
                      min = j;
                  }
              }
              // 将找到的最小值和i位置所在的值进行交换
              if (i != min){
                  int temp = arr[i];
                  arr[i] = arr[min];
                  arr[min] = temp;
              }
          }
          return arr;
      }

      private static void print(int[] arr){
          for(int i : arr){
              System.out.print(i + " ");
          }
      }

      public static void main(String[] args) {
          int[] arr01 = {3, 1, 5, 4, 9, 7, 6};
          int[] result = sort(arr01);
          print(result);
      }
  }

  • Python实现:

      def selectSort(arr):
  	for i in range(len(arr)-1):
  		for j in range(i+1, len(arr)):
  			if arr[i] > arr[j]:
  				arr[i], arr[j] = arr[j], arr[i]

  arr1 = [3, 7, 1, 8, 11, 2]
  selectSort(arr1)
  print(arr1)

  def improvedSelectionSort(arr):
  	max = 0
  	for i in range(len(arr) - 1):
  		max = i
  		for j in range(i+1, len(arr)):
  			if arr[j] > arr[max]:
  				max = j
  		if max != i:
  			arr[max], arr[i] = arr[i], arr[max]

  arr2 = [2, 9, 1, 5, 4]
  improvedSelectionSort(arr2)
  print(arr2)

  def improvedSelectionSort2(arr):
  	min = 0
  	for i in range(len(arr) - 1):
  		min = i
  		for j in range(i+1, len(arr)):
  			if arr[j] < arr[min]:
  				min = j
  		if min != i:
  			arr[min], arr[i] = arr[i], arr[min]

  arr3 = [7, 4, 8, 1, 3, 11, 9]
  improvedSelectionSort2(arr3)
  print(arr3)

  • Golang实现:

        package main

  import "fmt"

  func main()  {
  	var arr = []int{3, 4, 1, 7, 5, 9}
  	var arr2 = selectSort(arr)
  	fmt.Println(arr2)

  }

  func selectSort (arr []int) []int{
  	var i, j int

  	for i = 0; i < len(arr) - 1; i++ {
  		min := i
  		for j = i + 1; j < len(arr); j++{
  			if arr[min] > arr[j] {
  				min = j
  			}
  		}
  		arr[i], arr[min] = arr[min], arr[i]
  	}
  	return  arr
  }

  • Scala实现:

      package com.ronnie.scala

  	object SelectSort {

  	  def sort(array: Array[Int]): Array[Int] = {
  	    
  	    for(i <- 0 until(array.length - 1)){
  	      var min = i
  	      for(j <- i + 1 until array.length ){
  	        if (array(min) > array(j)){
  	           min = j
  	        }
  	      }
  	      if (i != min){
  	        val temp = array(i)
  	        array(i) = array(min)
  	        array(min) = temp
  	      }
  	    }
  	    array
  	  }

  	  def main(args: Array[String]): Unit = {
  	    val arr01 = Array[Int](3, 1, 2, 7, 4, 6)
  	    val result = sort(arr01)
  	    printArray(result)
  	  }

  	  def printArray(array: Array[Int]): Unit = {
  	    array.foreach(println)
  	  }
  	}

插入排序

  • Java实现:

        package com.ronnie.algorithm.sort;

  import java.util.Arrays;

  public class InsertSort {

      private static int[] sort(int[] arr){
          // 对 arr 进行拷贝, 不改变参数内容
          int[] arrCopy = Arrays.copyOf(arr, arr.length);

          // 从下标为1的元素开始选择合适的位置插入, 因为下标为0的只有一个元素, 默认是有序的
          for (int i = 1; i< arr.length; i++){

              // 记录要插入的数据
              int temp = arr[i];

              // 从已经排序的序列最右边的开始比较, 找到比其小的数
              int j = i;
              while (j > 0 && temp < arr[j - 1]){
                  arr[j] = arr[j - 1];
                  j--;
              }
              // 存在比其小的数, 插入
              if (j != i){
                  arr[j] = temp;
              }
          }
          return arr;
      }

      private static void print(int[] arr){
          for(int i : arr){
              System.out.print(i + " ");
          }
      }

      public static void main(String[] args) {
          int[] arr01 = {3, 1, 5, 4, 9, 7, 6};
          int[] result = sort(arr01);
          print(result);
      }
  }

  • Python实现:

        def insertSort(arr):
  	n = len(arr)
  	for i in range(n-1):
  		for j in range(i+1, 0, -1):
  			if arr[j]< arr[j - 1]:
  				arr[j], arr[j - 1] = arr[j - 1], arr[j]
  			else:
  				break

  arr1 = [3, 1, 2, 7, 5, 6]
  insertSort(arr1)
  print(arr1)

  • Golang实现:

        	package main

  import "fmt"

  func main()  {
  	var arr = []int{3, 4, 1, 7, 5, 9}
  	var arr2 = insertSort(arr)
  	fmt.Println(arr2)
  }

  func insertSort (arr []int) []int {
  	for i := range arr{
  		preIndex := i - 1
  		current := arr[i]
  		for preIndex >= 0 && arr[preIndex] < current{
  			arr[preIndex + 1] = arr[preIndex]
  			preIndex -= 1
  		}
  		arr[preIndex + 1] = current
  	}
  	return arr
  }

  • Scala实现:

        package com.ronnie.scala



  object InsertSort {

    def sort(array: Array[Int]): Array[Int] = {
        // 对arr 进行拷贝, 不改变参数内容
        val arrCopy = array.clone()

        // 从下标为1的元素开始选择合适的位置插入, 因为下标为0的只有一个元素, 默认是有序的
        for(i <- 1 until arrCopy.length){
          // 记录要插入的数据
          val temp = arrCopy(i)

          // 从已经排序的序列最右边的开始比较, 找到比其小的数
          var j = i
          while (j > 0 && temp < arrCopy(j - 1)){
            arrCopy(j) = arrCopy(j - 1)
            j -= 1
          }

          // 存在比其小的数, 插入
          if (j != i){
            arrCopy(j) = temp
          }
        }
       arrCopy
    }

    def main(args: Array[String]): Unit = {
      val arr01 = Array[Int](3, 1, 2, 7, 4, 6)
      val result = sort(arr01)
      printArray(result)
    }

    def printArray(array: Array[Int]): Unit = {
      array.foreach(println)
    }
  }

希尔排序

  • Java实现:
        package com.ronnie.algorithm.sort;

  import java.util.Arrays;

  public class ShellSort {

      private static int[] sort(int[] arr){
       // 对 arr 进行拷贝, 不改变参数内容
       int[] arrCopy = Arrays.copyOf(arr, arr.length);

       int gap = 1;
       while (gap < arrCopy.length){
          gap = gap * 3 + 1;
        }

       while (gap > 0){
           for (int i = gap; i < arrCopy.length; i++){
               int temp = arrCopy[i];
               int j = i - gap;
               while (j >= 0 && arrCopy[j] > temp){
                   arrCopy[j + gap] = arrCopy[j];
                   j -= gap;
               }
               arrCopy[j + gap] = temp;
           }
           gap = (int)Math.floor(gap / 3);
       }
       return arrCopy;
      }

      private static void print(int[] arr){
          for(int i : arr){
              System.out.print(i + " ");
          }
      }

      public static void main(String[] args) {
          int[] arr01 = {3, 1, 5, 4, 9, 7, 6};
          int[] result = sort(arr01);
          print(result);
      }
  }
  • Python实现:
        def shellSort(arr):
  	import math
  	gap = 1 #增量
  	while(gap < len(arr)/3):
  		gap = gap*3 + 1
  	while(gap > 0):
  		for i in range(gap, len(arr)):
  			temp = arr[i]
  			j = i - gap
  			while j >= 0 and arr[j] > temp:
  				arr[j+gap] = arr[j]
  				j -= gap
  			arr[j+gap] = temp
  		gap = math.floor(gap/3)
  	return arr
  				
  			
  arr1 = [3, 1, 2, 7, 4, 6, 9]
  print(shellSort(arr1))
  • Golang实现:
        package main

  import (
  	"fmt"
  )

  func main()  {
  	var arr = []int{3, 4, 1, 7, 5, 9}
  	var arr2 = shellSort(arr)
  	fmt.Println(arr2)
  }

  func shellSort(arr [] int) [] int{
  	length := len(arr)
  	gap := 1
  	for gap < length{
  		gap = gap * 3 + 1
  	}
  	for gap > 0{
  		for i := gap; i < len(arr); i++ {
  			temp := arr[i]
  			j := i - gap
  			for j >= 0 && arr[j] > temp{
  				arr[j + gap] = arr[j]
  				j -= gap
  			}
  			arr[j + gap] = temp
  		}
  		gap = gap / 3
  	}
  	return arr
  }
  • Scala实现:
      package com.ronnie.scala

  object ShellSort {

    def sort(array: Array[Int]): Array[Int] = {
      var gap = 1
      while (gap < array.length){
        gap = gap * 3 + 1
      }
      while (gap > 0){
        for (i <- gap until array.length){
          val temp = array(i)
          var j = i - gap
          while (j >= 0 && array(j) > temp){
            array(j + gap) = array(j)
            j -= gap
          }
          array(j + gap) = temp
        }
        gap = gap / 3
      }
      array
    }
    def main(args: Array[String]): Unit = {
      val arr01 = Array[Int](3, 1, 2, 7, 4, 6)
      val result = sort(arr01)
      printArray(result)
    }

    def printArray(array: Array[Int]): Unit = {
      array.foreach(println)
    }
  }

归并排序

  • Java实现:

        package com.ronnie.algorithm.sort;

  import java.util.Arrays;

  public class MergeSort {

      private static int[] sort(int[] arr){
          int[] arrCopy = Arrays.copyOf(arr, arr.length);

          // 长度小于2意味着已经归并完成了
          if (arrCopy.length < 2){
              return arrCopy;
          }
          // 二分法获取中间位置
          int middle = (int) Math.floor(arrCopy.length / 2);

          // 左侧数组
          int[] left = Arrays.copyOfRange(arrCopy, 0, middle);
          // 右侧数组
          int[] right = Arrays.copyOfRange(arrCopy, middle, arrCopy.length);

          // 递归合并排序后的左右数组
          return merge(sort(left), sort(right));
      }

      /**
       *  默认 left 与 right数组都已经排序好了
       * @param left
       * @param right
       * @return
       */
      private static int[] merge(int[] left, int[] right){
          // 初始化结果数组
          int[] result = new int[left.length + right.length];

          int i = 0;
          // 左右数组存在且有值, 使用while优化递归
          while (left.length > 0 && right.length > 0){
              // 比较左侧数组头与右侧数组头
              if (left[0] <= right[0]){
                  // 递归取出较小的数组头放入到结果数组中
                  result[i++] = left[0];
                  left = Arrays.copyOfRange(left, 1, left.length);
              } else {
                  // 递归取出较小的数组头放入到结果数组中
                  result[i++] = right[0];
                  right = Arrays.copyOfRange(right, 1, right.length);
              }
          }
          // 左数组存在有值
          while (left.length > 0){
              // 递归取出较小的数组头放入到结果数组中
              result[i++] = left[0];
              left = Arrays.copyOfRange(left, 1, left.length);
          }
          // 右数组存在且有值
          while (right.length > 0){
              // 递归取出较小的数组头放入到结果数组中
              result[i++] = right[0];
              right = Arrays.copyOfRange(right, 1, right.length);
          }
          return result;
      }

      private static void print(int[] arr){
          for(int i : arr){
              System.out.print(i + " ");
          }
      }

      public static void main(String[] args) {
          int[] arr01 = {3, 1, 5, 4, 9, 7, 6};
          int[] result = sort(arr01);
          print(result);
      }
  }

  • Python实现:

        def mergeSort(arr):
  	import math
  	if(len(arr) < 2):
  		return arr
  	middle = math.floor(len(arr)/2)	
  	left, right = arr[0:middle], arr[middle:]
  	return merge(mergeSort(left), mergeSort(right))

  def merge(left, right):
  	result = []
  	# 左右数组存在且有值, 使用while优化递归
  	while left and right:
  		# 比较左侧数组头与右侧数组头
  		if left[0] < right[0]:
  			# 递归取出较小的数组头放入到结果数组中
  			result.append(left[0])
  			left = left[1:]
  		else:
  			# 递归取出较小的数组头放入到结果数组中
  			result.append(right[0])
  			right = right[1:]
  	# 左数组存在有值		
  	while left:
  		# 递归取出数组头放入到结果数组中
  		result.append(left[0])
  		left = left[1:]
  	# 右数组存在且有值	
  	while right:
  		# 递归取出数组头放入到结果数组中
  		result.append(right[0])
  		right = right[1:]
  	return result	


  arr01 = [4, 1, 7, 3, 2, 5, 6]
  res = mergeSort(arr01)
  print(res)

  • Golang实现:

        package main

  import "fmt"

  func main()  {
  	var arr = []int{3, 4, 1, 7, 5, 9}
  	var arr2 = mergeSort(arr)
  	fmt.Println(arr2)
  }

  func mergeSort(arr [] int) [] int {

  	length := len(arr)
  	if len(arr) < 2 {
  		return arr
  	}
  	middle := length / 2
  	left := arr[0 : middle]
  	right := arr[middle : length]

  	return merge(mergeSort(left), mergeSort(right))
  }

  func merge(left[] int, right[] int) [] int {
  	var result [] int

  	// 左右数组存在且有值, 使用for优化递归
  	for len(left) > 0 && len(right) > 0{
  		if left[0] < right[0]{
  			// 递归取出较小的数组头放入到结果数组中
  			result = append(result, left[0])
  			left = left[1:]
  		} else {
  			// 递归取出较小的数组头放入到结果数组中
  			result = append(result, right[0])
  			right = right[1:]
  		}
  	}

  	for len(left) > 0{
  		// 递归取出数组头放入到结果数组中
  		result = append(result, left[0])
  		left = left[1:]
  	}

  	for len(right) > 0{
  		// 递归取出数组头放入到结果数组中
  		result = append(result, right[0])
  		right = right[1:]
  	}
  	return result
  }

  • Scala实现:

    • 该段代码发生了OOM......
       package com.ronnie.scala

  import scala.collection.mutable.ArrayBuffer

  object MergeSort {

    def sort(array: ArrayBuffer[Int]): ArrayBuffer[Int] = {

      if (array.length < 2){
        return array
      }

      val middle = array.length / 2

      val left = array.slice(0, middle)
      val right = array.slice(middle, array.length)
      merge(sort(left), sort(right))
    }

    def merge(left: ArrayBuffer[Int], right: ArrayBuffer[Int]): ArrayBuffer[Int] = {

      var leftTemp = left

      var rightTemp = right

      val result: ArrayBuffer[Int] = new ArrayBuffer[Int]()

      while (leftTemp.nonEmpty && rightTemp.nonEmpty){
        if (leftTemp(0) < rightTemp(0)){
          result.append(left(0))
          leftTemp = leftTemp.slice(1, leftTemp.length)
        } else {
          result.append(right(0))
          rightTemp = rightTemp.slice(1, rightTemp.length)
        }
      }
      while (left.nonEmpty){
        result.append(left(0))
        leftTemp = leftTemp.slice(1, leftTemp.length)
      }
      while (right.nonEmpty){
        result.append(right(0))
        rightTemp = rightTemp.slice(1, rightTemp.length)
      }
      result
    }

    def main(args: Array[String]): Unit = {
      val arr01 = ArrayBuffer[Int](3, 1, 2, 7, 4, 6)
      val result = sort(arr01)
      printArray(result)
    }

    def printArray(array: ArrayBuffer[Int]): Unit = {
      array.foreach(println)
    }
  }

快速排序

  • Java实现:

        package com.ronnie.algorithm.sort;

  import java.util.Arrays;

  public class QuickSort {

      private static int[] sort(int[] arr){
          // 对 arr 进行拷贝, 不改变参数内容
          int[] arrCopy = Arrays.copyOf(arr, arr.length);

          return quickSort(arrCopy, 0, arr.length);
      }

      private static int[] quickSort(int[] arr, int left, int right){
          // 如果数组有数值
          if (left < right){
              // 执行分区操作, 获取分区参数(即是该次分区的pivot的值)
              int partitionIndex = partition(arr, left, right);
              // 递归地 对小于基准值的子数列 进行快排
              quickSort(arr, left, partitionIndex - 1);
              // 递归地 对大于基准值的子数列 进行快排
              quickSort(arr, partitionIndex + 1, right);
          }
          // 若没数值直接返回空数组
          return arr;
      }

      private static int partition(int[] arr, int left, int right){
          // 设定基准值 pivot
          int pivot = left;
          // index 初始为 pivot 后一位参数
          int index = pivot + 1;
          for (int i = index; i < right; i++){
              // 如果 pivot节点 后的参数 < pivot 节点的参数, 就将 该参数与 index 参数进行交换
              if (arr[i] < arr[pivot]){
                  swap(arr, i, index);
                  // 将index 逐渐向后移动
                  index++;
              }
          }
          // 交换 pivot 与 最终的index位置前一位
          swap(arr, pivot, index - 1);
          // 所以返回的其实是交换前的 pivot 的值
          return index - 1;
      }

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

      private static void print(int[] arr){
          for(int i : arr){
              System.out.print(i + " ");
          }
      }

      public static void main(String[] args) {
          int[] arr01 = {3, 1, 5, 4, 9, 7, 6};
          int[] result = sort(arr01);
          print(result);
      }
  }

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


  arr01 = [4, 1, 7, 3, 2, 5, 6]
  res = quickSort(arr01, 0, 6)
  print(res)

  • Golang实现:

      package main

  import "fmt"

  func main()  {
  	var arr = []int{3, 4, 1, 7, 5, 9, 8}
  	var arr2 = sort(arr)
  	fmt.Println(arr2)
  }

  func sort(arr[] int) []int {
  	return quickSort(arr, 0, len(arr))
  }

  func quickSort(arr [] int, left, right int) []int {
  	// 如果数组有数值
  	if left < right{
  		// 执行分区操作, 获取分区参数(即是该次分区的pivot的值)
  		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 后一位参数
  	index := pivot + 1

  	for i := index; i < right; i++ {
  		// 如果 pivot 节点后的参数 < pivot 节点的参数, 就将 改参数 与 index 参数进行交换
  		if arr[i] < arr[pivot]{
  			swap(arr, i, index)
  			// 将index 逐渐向后移动
  			index++
  		}
  	}
  	// 交换 pivot 与 最终的 index 位置前一位
  	swap(arr, pivot, index - 1)
  	// 所以返回的其实是交换前 pivot 的值
  	return index - 1
  }

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

  • Scala实现:

    • 还是有问题, lzzscl, 明明感觉思路没毛病, scala坑好多。
        package com.ronnie.scala

  object QuickSort {

    def sort(array: Array[Int]): Array[Int] = {
      quickSort(array, 0, array.length)
    }

    def quickSort(array: Array[Int], left: Int, right: Int ): Array[Int] = {
      if (left < right){
        val partitionIndex = partition(array, left, right)
        quickSort(array, left, partitionIndex - 1)
        quickSort(array, partitionIndex + 1, right)
      }
      array
    }

    def partition(array: Array[Int], left: Int, right: Int): Int = {
      val pivot = left
      var index = pivot + 1
      var i = index
      while (i < right){
        if (array(i) < array(pivot)){
          swap(array, i, index)
          index += 1
        }
        i += 1
      }
      swap(array, pivot, index - 1)
      index - 1
    }

    def swap(array: Array[Int], i: Int, j: Int): Unit ={
      val temp = array(i)
      array(i) = array(j)
      array(j) = temp
    }

    def main(args: Array[String]): Unit = {
      val arr01 = Array[Int](3, 1, 2, 7, 4, 6)
      val result = sort(arr01)
      printArray(result)
    }

    def printArray(array: Array[Int]): Unit = {
      array.foreach(println)
    }
  }

堆排序

  • Java实现:
        package com.ronnie.algorithm.sort;

  import java.util.Arrays;

  public class HeapSort {

      private static int[] sort(int[] arr){
          int[] arrCopy = Arrays.copyOf(arr, arr.length);

          int len = arrCopy.length;

          // 创建大顶堆
          buildMaxHeap(arrCopy, len);

          for (int i = len - 1; i > 0; i--){
              swap(arrCopy, 0, i);
              len--;
              heapify(arrCopy, 0, len);
          }
          return arrCopy;
      }

      /**
       *  建立大顶堆
       * @param arr
       * @param len
       */
      private static void buildMaxHeap(int[] arr, int len){
          // 将数组分为一个个二叉堆, 后序遍历
          for (int i = (int) Math.floor(len / 2); i >= 0; i--){
              // 递归进行堆化
              heapify(arr, i, len);
          }
      }

      /**
       *  堆化, 设置最小二叉堆
       * @param arr
       * @param i
       * @param len
       */
      private static void heapify(int[] arr, int i, int len){
          // 堆左
          int left = 2 * i + 1;
          // 堆右
          int right = 2 * i + 2;
          // 将i位置的数设为初始最大值
          int largest = i;
          
          // 如果堆左不为末尾, 且堆左的值 > 最大值, 就将堆左的值设为最大值
          if (left < len && arr[left] > arr[largest]){
              largest = left;
          }
          
          // 如果堆右不为末尾, 且堆右的值 > 最大值, 就将堆右的值设为最大值
          if (right < len && arr[right] > arr[largest]){
              largest = right;
          }
          // 如果最大值的位置不是初始位置
          if (largest != i){
              // 交换最大值和初始值
              swap(arr, i, largest);
              // 对初始值递归执行堆化
              heapify(arr, largest, len);
          }
      }
      private static void swap(int[] arr, int i, int j){
          int temp = arr[i];
          arr[i] = arr[j];
          arr[j] = temp;
      }

      private static void print(int[] arr){
          for(int i : arr){
              System.out.print(i + " ");
          }
      }

      public static void main(String[] args) {
          int[] arr01 = {3, 1, 5, 4, 9, 7, 6};
          int[] result = sort(arr01);
          print(result);
      }
  }
  • Python实现:
        import math

  def heapSort(arr):
  	global length
  	length = len(arr)
  	# 创建大顶堆
  	buildMaxHeap(arr)

  	for i in range(len(arr) - 1, 0, -1):
  		swap(arr, 0, i)
  		length -= 1
  		heapify(arr, 0)
  	return arr	

  def buildMaxHeap(arr):
  	for i in range((length//2), -1, -1): # 注意这个地方是要能取到0的
  		heapify(arr, i)

  def heapify(arr, i):
  	left = 2 * i + 1
  	right = 2 * i + 2
  	largest = i

  	if left < length and arr[left] > arr[largest]:
  		largest = left

  	if right < length and arr[right] > arr[largest]:
  		largest = right

  	if largest is not i:
  		swap(arr, i, largest)
  		heapify(arr, largest)		 

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

  arr01 = [4, 1, 7, 3, 2, 5, 6]
  res = heapSort(arr01)
  print(res)
  • Golang实现:
        package main

  import "fmt"

  func main()  {
  	var arr = []int{3, 4, 1, 7, 5, 9, 6}
  	var arr2 = heapSort(arr)
  	fmt.Println(arr2)
  }

  func heapSort(arr[] int) [] int{
      length := len(arr)

      // 创建大顶堆
      buildMaxHeap(arr, length)

  	for i := length - 1; i > 0; i-- {
  		swap02(arr, 0, i)
  		length--
  		heapify(arr, 0, length)
  	}
  	return  arr
  }

  func buildMaxHeap(arr[] int, len int)  {
  	for i := len / 2; i >= 0; i--{
  		heapify(arr, i, len)
  	}
  }

  func heapify(arr[] int, i int, len int)  {
  	left := 2 * i + 1
  	right := 2 * i + 2
  	largest := i

  	if left < len && arr[left] > arr[largest]{
  		largest = left
  	}

  	if right < len && arr[right] > arr[largest]{
  		largest = right
  	}
  	if largest != i{
  		swap02(arr, i, largest)
  		heapify(arr, largest, len)
  	}
  }

  func swap02(arr[] int, i int, j int)  {
  	arr[i], arr[j] = arr[j], arr[i]
  }
  • Scala实现:
        package com.ronnie.scala

  object HeapSort {
    def sort(array: Array[Int]): Array[Int] = {
      var len = array.length

      // 创建大顶堆
      buildMaxHeap(array, len)

      for (i <- len - 1 until(0, -1)){
        swap(array, 0 , i)
        len -= 1
        heapify(array, 0, len)
      }
      array
    }

    def buildMaxHeap(array: Array[Int], len: Int): Unit ={
       for ( i <- len/2 until(-1, -1)){
         heapify(array, i, len)
       }
    }

    def heapify(array: Array[Int], i: Int, len: Int): Unit ={
      val left = 2 * i + 1
      val right = 2 * i + 2
      var largest = i

      if (left < len && array(left) > array(largest)){
        largest = left
      }
      if (right < len && array(right) > array(largest)){
        largest = right
      }
      if (largest != i){
        swap(array, i, largest)
        heapify(array, largest, len)
      }
    }
    def swap(array: Array[Int], i: Int, j: Int): Unit ={
      val temp = array(i)
      array(i) = array(j)
      array(j) = temp
    }

    def main(args: Array[String]): Unit = {
      val arr01 = Array[Int](3, 1, 2, 7, 4, 6)
      val result = sort(arr01)
      printArray(result)
    }

    def printArray(array: Array[Int]): Unit = {
      array.foreach(println)
    }
  }

计数排序

  • Java实现:
        package com.ronnie.algorithm.sort;

  import java.util.Arrays;

  public class CountingSort {

      private static int[] sort(int[] arr){
          int[] arrCopy = Arrays.copyOf(arr, arr.length);

          int maxValue = getMaxValue(arrCopy);

          return countingSort(arrCopy, maxValue);
      }

      private static int[] countingSort(int[] arr, int maxValue){
          // 桶数组长度 为最大值 + 1
          int bucketLen = maxValue + 1;
          // 初始化桶
          int[] bucket= new int[bucketLen];

          /*
              将数组中的数值放入桶中, 并根据个数占位
              简单理解: 有 10 个年龄不同的人，统计出有 8 个人的年龄比 A 小，那 A 的年龄就排在第 9 位
           */
          for (int value : arr){
              bucket[value]++;
          }
          // 初始化排序参数为0
          int sortedIndex = 0;
          for (int j = 0; j < bucketLen; j++){
              // 反向填充数组, 并将每个数的统计减去1, 以保证稳定性
              while (bucket[j] > 0){
                  arr[sortedIndex++] = j;
                  bucket[j]--;
              }
          }
          return arr;
      }

      /**
       *  找出待排序的数组中最大的元素
       * @param arr
       * @return
       */
      private static  int getMaxValue(int[] arr){
          int maxValue = arr[0];
          for (int value : arr){
              if (maxValue < value){
                  maxValue = value;
              }
          }
          return maxValue;
      }

      private static void print(int[] arr){
          for(int i : arr){
              System.out.print(i + " ");
          }
      }

      public static void main(String[] args) {
          int[] arr01 = {3, 1, 5, 4, 9, 7, 6};
          int[] result = sort(arr01);
          print(result);
      }
  }
  • Python实现:
        def sort(arr):
  	maxValue = getMaxValue(arr)
  	return countingSort(arr, maxValue)

  def getMaxValue(arr):
  	maxValue = arr[0]
  	for v in arr:
  		if maxValue < v:
  			maxValue = v
  	return maxValue		


  def countingSort(arr, maxValue):
  	bucketLen = maxValue + 1
  	# 初始化值为0 且 大小为 bucketLen 的桶
  	bucket = [0]*bucketLen
  	# 初始化排序参数
  	sortedIndex = 0
  	length = len(arr)
  	# 将数组中的数值放入桶中, 并根据个数占位
  	for i in range(length):
  		if not bucket[arr[i]]:
  			bucket[arr[i]] = 0
  		bucket[arr[i]] += 1
  	# 反向填充数组, 并将每个数的统计减去1, 以保证稳定性	
  	for j in range(bucketLen):
  		while bucket[j]	> 0:
  			arr[sortedIndex] = j
  			sortedIndex += 1
  			bucket[j] -= 1
  	return arr		

  arr01 = [4, 1, 7, 3, 2, 5, 6]
  res = sort(arr01)
  print(res)
  • Golang实现:
        package main

  import "fmt"

  func main()  {
  	var arr = []int{3, 4, 1, 7, 5, 9, 6}
  	var arr2 = sort03(arr)
  	fmt.Println(arr2)
  }

  func sort03(arr [] int) [] int {
  	maxValue := getMaxValue(arr)
  	return countingSort(arr, maxValue)
  }

  func countingSort(arr [] int, maxValue int) [] int {
  	bucketLen := maxValue + 1

  	// 初始为0的数组
  	bucket := make([] int, bucketLen)

  	sortedIndex := 0

  	length := len(arr)

  	// 将数组中的数值放入桶中, 并根据个数占位
  	for i := 0; i < length; i++ {
  		bucket[arr[i]] += 1
  	}

  	// 反向填充数组, 并将每个数的统计减去1, 以保证稳定性
  	for j := 0; j < bucketLen; j++{
  		for bucket[j] > 0{
  			arr[sortedIndex] = j
  			sortedIndex += 1
  			bucket[j] -= 1
  		}
  	}
  	return arr
  }
  // 获取最大值
  func getMaxValue(arr [] int) int {
  	maxValue := arr[0]
  	for i := 1; i < len(arr); i++ {
  		if maxValue < arr[i]{
  			maxValue = arr[i]
  		}
  	}
  	return maxValue
  }
  • Scala实现:
        package com.ronnie.scala

  object CountingSort {

    def sort(array: Array[Int]): Array[Int] = {
      val maxValue =  getMaxValue(array)

      countingSort(array, maxValue)
    }

    def countingSort(array: Array[Int], maxValue: Int): Array[Int] ={
      val bucketLen = maxValue + 1

      val bucket = new Array[Int](bucketLen)

      var sortedIndex = 0

      val length = array.length

       // 将数组中的数值放入桶中, 并根据个数占位
        for (i <- 0 until length){
          bucket(array(i)) += 1
        }

       // 反向填充数组, 并将每个数的统计减去1, 以保证稳定性
      for (j <- 0 until bucketLen){
        while (bucket(j) > 0){
            array(sortedIndex) = j
            sortedIndex += 1
            bucket(j) -= 1
        }
      }
      array
    }

    def getMaxValue(array: Array[Int]):Int = {
      array.max
    }

    def main(args: Array[String]): Unit = {
      val arr01 = Array[Int](3, 1, 2, 7, 4, 6)

      val result = sort(arr01)
      printArray(result)

    }

    def printArray(array: Array[Int]): Unit = {
      array.foreach(println)
    }
  }

桶排序

  • Java实现:
        package com.ronnie.algorithm.sort;

  import java.util.Arrays;

  public class BucketSort {

      private static int[] sort(int[] arr){
          int [] arrCopy = Arrays.copyOf(arr, arr.length);

          return  bucketSort(arrCopy, 5);
      }

      private static int[] bucketSort(int[] arr, int bucketSize){
          if (arr.length == 0){
              return arr;
          }

          int minValue = arr[0];
          int maxValue = arr[0];
          for (int value : arr){
              if (value < minValue){
                  minValue = value;
              } else if ( value > minValue){
                  maxValue = value;
              }
          }

          int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize + 1);
          int [][] buckets = new int[bucketCount][0];

          // 利用映射函数将数据分配到各个桶中
          for (int item : arr) {
              int index = (int) Math.floor((item - minValue) / bucketSize);
              buckets[index] = arrAppend(buckets[index], item);
          }

          int arrIndex = 0;

          for (int[] bucket : buckets){
              if (bucket.length <= 0){
                  continue;
              }
              // 对每个桶进行排序, 这里使用插排
              bucket = InsertSort.sort(bucket);
              for (int value : bucket){
                  arr[arrIndex++] = value;
              }
          }
          return arr;
      }

      /**
       *  自动扩容, 并保存数据
       * @param arr
       * @param value
       * @return
       */
      private static int[] arrAppend(int[] arr, int value){
          arr = Arrays.copyOf(arr, arr.length + 1);
          arr[arr.length - 1] = value;
          return arr;
      }

      private static void print(int[] arr){
          for(int i : arr){
              System.out.print(i + " ");
          }
      }

      public static void main(String[] args) {
          int[] arr01 = {3, 1, 5, 4, 9, 7, 6};
          int[] result = sort(arr01);
          print(result);
      }
  }
  • Python实现:
        def insertionSort(b):
  	for i in range(1, len(b)):
  		up = b[i]
  		j = i - 1
  		while j >= 0 and b[j] > up:
  			b[j + 1] = b[j]
  			j -= 1
  		b[j + 1] = up
  	return b

  def bucketSort(x):
  	arr = []
  	slot_num = 10 # 10 means 10 slots, each 
  				  # slot's size is 0.1
  	for i in range(slot_num):
  		arr.append([])

  	# Put array elements in different buckets
  	for j in x:
  		index_b = int(slot_num * j)
  		arr[index_b].append(j)

  	# Sort individual buckets
  	for i in range(slot_num):
  		arr[i] = insertionSort(arr[i])

  	# concatenate the result
  	k = 0
  	for i in range(slot_num):
  		for j in range(len(arr[i])):
  			x[k] = arr[i][j]
  			k += 1
  	return x

  x = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]
  print(bucketSort(x))
  • Golang实现:
        package main

  import (
  	"container/list"
  	"fmt"
  )

  func main()  {
  	var arr01 = []int{10, 1, 18, 30, 23, 12, 7, 5, 18, 17}
  	bucketSort(arr01, len(arr01))
  }

  func bucketSort(array [] int, num int)  {
  	var bucket [99]int
  	for i:=0; i < len(array); i++{
  		bucket[10] = 1
  		if bucket[array[i]] != 0{
  			bucket[array[i]] = bucket[array[i]] + 1
  		} else {
  			bucket[array[i]] = 1
  		}
  	}
  	l := list.New()
  	for j := 0; j < len(array); j++{
  		if array[j] == 0{
  			panic(" sth wrong")
  		} else {
  			for k := 0; k < array[j]; k++{
  				l.PushBack(j)
  			}
  		}
  	}
  	for e := l.Front(); e != nil; e = e.Next(){
  		fmt.Print(e.Value, " ")
  	}
  }
  • Scala实现:
        package com.ronnie.scala


  object BucketSort {
      def sort(arr: Array[Int]): Array[Int] = {
        if (arr.length <= 1) return arr
        val bucket = new Array[Int](10)
        for (i <- arr.indices){
          bucket(arr(i)) += 1
        }
        for (i <- bucket.indices){
          if (bucket(i) != 0){
            for(j <- 1 to bucket(i)){
              print(s"$i")
            }
          }
        }
        arr
      }

    def main(args: Array[String]): Unit = {
      val arr01 = Array[Int](1, 3, 4, 2, 5, 5, 6, 9, 3, 4, 4)
      val result = sort(arr01)
      printArray(result)

    }

    def printArray(array: Array[Int]): Unit = {
      array.foreach(println)
    }
  }

基数排序

  • Java实现:

        package com.ronnie.algorithm.sort;

  public class RadixSort {

      private static void radixSort(int[] arr, int max){
          // 计数数组
          int[] count = new int[arr.length];

          // 初始化桶
          int[] bucket = new int[arr.length];

          // k: 第几位, 1代表个位, 2代表十位, 3代表百位
          for(int k = 1; k < max; k++){

              // 把count置空, 防止上次循环的数据影响
              for (int i = 0; i < arr.length; i++){
                  count[i] = 0;
              }

              /*
                 分别统计第k位是0,1,2,3,4,5,6,7,8,9 的数量
                 以下循环用于统计每个桶中的数据的数量
               */
              for (int value : arr) {
                  count[getFigure(value, k)]++;
              }

              // 利用count[i]来确定放置数据的位置
              for (int i = 1; i < arr.length; i++){
                  count[i] = count[i] + count[i - 1];
              }

              // 执行完此循环之后的count[i]就是第i个桶右边界的位置

              /*
                 利用循环把数据从后往前装入各个桶中
               */

              for (int i = arr.length - 1; i >= 0; i--){
                  int j = getFigure(arr[i], k);
                  bucket[count[j] - 1] = arr[i];
                  count[j]--;
              }

              // 将桶中的数据取出来, 赋值给arr
              System.arraycopy(bucket, 0, arr, 0, arr.length);
          }
      }

      /**
       *  返回int型数i的第k位是什么
       * @param i
       * @param k
       * @return
       */
      private static int getFigure(int i, int k){
          int[] a = {1, 10, 100};
          return (i / a[k - 1] % 10);
      }

      private static void print(int[] arr){
          for(int i : arr){
              System.out.print(i + " ");
          }
      }

      public static void main(String[] args) {
          int[] arr = {21,56,88,195,354,1,35,12,6,7,131,17,2};

          radixSort(arr, 3);

          print(arr);
      }
  }

  • Python实现:

        def radixSort(arr):
  	i = 0  # 记录当前正在排哪一位, 最低为1
  	max_num = max(arr)  # 获取数组最大值
  	j = len(str(max_num))  # 记录最大值位数
  	while i < j:
  		bucket_list = [[] for _ in range(10)] # 初始化桶数组
  		for x in arr:
  			bucket_list[int(x / (10 ** i) % 10)].append(x)  # 找到位置放入桶数组
  		print(bucket_list)	
  		arr.clear()
  		for x in bucket_list: # 放回原序列
  			for y in x:
  				arr.append(y)
  		i += 1	
  		
  arr01 = [334,5,67,345,7,345345,99,4,23,78,45,1,3453,23424]		
  radixSort(arr01)

  • Golang实现:

    package main

  import "fmt"

  func main()  {
  	arr := [] int {21,56,88,195,354,1,35,12,6,7,131,17,2}

  	radixSort(arr, 3)

  	fmt.Print(arr)
  }

  func radixSort(arr [] int, max int) {
  	count := make([] int, len(arr))

  	bucket := make([] int, len(arr))

  	// k: 第几位, 1代表个位, 2代表十位, 3代表百位
  	for k := 1; k < max; k++ {
  		// 把count置空, 防止上次循环的数据影响
  		for i := 0; i < len(arr); i++ {
  			count[i] = 0
  		}
  		/*
  		   分别统计第k位是0,1,2,3,4,5,6,7,8,9 的数量
  		   以下循环用于统计每个桶中的数据的数量
  		*/
  		for v := range arr{
  			count[getFigure(v, k)]++
  		}

  		// 利用count[i]来确定放置数据的位置
  		for i := 1; i < len(arr); i++ {
  			count[i] = count[i] + count[i - 1]
  		}

  		// 执行完此循环之后的count[i]就是第i个桶右边界的位置

  		/*
  		   利用循环把数据从后往前装入各个桶中
  		*/
  		for i := len(arr) - 1; i >= 0; i-- {
  			j := getFigure(arr[i], k)
  			bucket[count[j] - 1] = arr[i]
  			count[j]--
  		}

  		// 将桶中的数据取出来, 赋值给arr
  		for i := 0; i < len(bucket); i++{
  			arr[i] = bucket[i]
  		}
  	}
  }
  // 返回 int型数i的第k位是什么
  func getFigure(i int, k int) int {
  	a := []int{1, 10, 100}
  	return i / a[k - 1] % 10
  }

  • Scala实现:

        package com.ronnie.scala

  object RadixSort {

    def radixSort(array: Array[Int], max: Int): Unit ={
      val count = new Array[Int](array.length)
      val bucket = new Array[Int](array.length)

      // k: 第几位, 1代表个位, 2代表十位, 3代表百位
      for (k <- 1 until max){

        // 把count置空, 防止上次循环的数据影响
          for (i <- array.indices){
             count(i) = 0
          }
        /*
           分别统计第k位是0,1,2,3,4,5,6,7,8,9 的数量
           以下循环用于统计每个桶中的数据的数量
         */
          for (v <- array){
            count(getFigure(v, k)) += 1
          }

        // 利用count[i]来确定放置数据的位置
         for (i <- 1 until array.length){
           count(i) = count(i) + count(i - 1)
         }

        // 执行完此循环之后的count[i]就是第i个桶右边界的位置

        /*
           利用循环把数据从后往前装入各个桶中
         */
         for (i <- array.length - 1 to(0, -1)){
            val j = getFigure(array(i), k)
            bucket(count(j) - 1) = array(i)
            count(j) -= 1
         }

        // 将桶中的数据取出来, 赋值给arr
        for (i <- bucket.indices){
          array(i) = bucket(i)
        }
      }
    }

    def getFigure(i : Int, k : Int): Int ={
      val a = Array[Int](1, 10, 100)
      i / a(k - 1) % 10
    }

    def main(args: Array[String]): Unit = {
      val arr = Array[Int](21,56,88,195,354,1,35,12,6,7,131,17,2)
      radixSort(arr, 3)
      arr.foreach(x => printf("%d ", x))
    }
  }

推荐阅读