经典排序算法总结
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了经典排序算法总结，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含31451字，纯文字阅读大概需要45分钟。
内容图文
概述
选泡插, 快归堆希桶计基, 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)) } }
内容总结
以上是互联网集市为您收集整理的经典排序算法总结全部内容，希望文章能够帮你解决经典排序算法总结所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】