常用排序算法代码兑现

主要推送关于对算法的思考以及应用的消息。坚信学会如何思考一个算法比单纯地掌握100个知识点重要100倍。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎您的关注。

01

回顾

五天过去了,8个主要排序算法的思想和原理图解都已经推送完了,在这些推送中,我们详细分析讨论了

  1. 各种排序算法的时间、空间复杂度;
  2. 算法的稳定性;
  3. 算法的优化改进
  4. 算法的应用场景

如果您想了解或者进一步熟悉下这些算法原理,请参考之前五天的推送:

冒泡排序到快速排序做的那些优化

直接选择排序到堆排序做的那些改进

直接插入排序到希尔排序做的那些改进

归并排序算法的过程图解

不基于比较的基数排序原理图解

02

兑现代码

当我们详细研究了这些常用排序算法的基本实现原理之后,是时候写出这些排序算法的源代码了,也许这些代码在网上有更高效的实现,不过下面写的这些都是和之前说的算法原理和图都解密切相关,一 一对应的,主要是方便大家的理解。测试了几遍,有错误大家指出来吧。

使用了 Java 语言 和 C# 语言实现了这些算法,下面一 一列出。

几个算法中使用的一个交换函数,源码如下,

//swap element at i to at j private static void swap(int[] array, int i,int j){ int tmp = array[i]; array[i] = array[j]; array[j] = tmp; }

以下7种排序算法都实现了序列的非降序排列,函数参数代表的含义一般统一定义为:

  1. array: 待排序的数组,类型为一维整形数组
  2. n:元素个数
  3. i:一般为外层循环索引,或表示排序区或未排序的开始或结束索引
  4. j :一般为内层循环索引,或表示未排序区或排序的结束或开始索引
  5. lo:数组计算区间的开始索引
  6. hi:数组计算区间的结束索引
  7. d :分组长度
  8. k:分组索引

03

冒泡排序

//bubble sort public static void bubbleSort(int[] array, int n){ int i = 0;// loop int j = 0; // element index while(i < n) { for(j=0; j<n-i-1; j++){ if( array[j] > array[j+1] ){ //swap condition swap( array, j, j +1 ); } } i++; } }

04

快速排序

快速排序是很巧妙的实现算法,它选取一个轴点,每轮计算时,凡是轴点的移动都会空出一个位置,这个位置就是被调整后的关键码所代替,经过这种调整后,一轮下来轴点前的关键码都小于轴点,后的都大于。

注意 里层的两个while遍历条件,最后碰头的位置,就是这轮轴点的位置,记得给这个填上轴点值。

//quick sort public static void quickSort(int[] array, int lo, int hi){ if(lo>hi) return; int pivot = array[lo]; int i = lo; int j = hi; while( i<j ){ //get smaller after pivot //warning: while condition, here and next while //at least one item is >= while(i < j && array[j] >= pivot){ j--; } array[i] = array[j]; //so at j an element is void //get bigger before pivot while(i < j && array[i] < pivot){ i++; } array[j] = array[i]; // at i an element is to fill at j } //here, i bumps into j array[i] = pivot; //here, before index i smaller than pivot, after bigger than pivot // lo~i quick sort quickSort(array, lo, i-1); // i+1~hi quick sort quickSort(array, i+1, hi); }

05

直接选择排序

直接选择排序就是把每轮找出的最小值放到排序区的最后,代码实现简单。

//direct select sort public static void selectSort(int[] array, int n){ int i=0; //sorted last element int j=0; //unsorted first element while(i<n){ int min=array[i]; int index = i; for(j=i+1; j<n;j++){ if(array[j]<min){ min = array[j]; index = j; } } swap(array,i,index); i++; } }

06

堆排序

注意大根堆顶与未排序区的最后一个元素不断交换,直至未排序区的个数为0,整个序列完成排序。

堆排序算法比较容易出错的点:

  1. 构建堆函数,左右子节点可能都有,也可能只含有左节点,咖啡色标记的代码
  2. 堆排序函数,while遍历时,buildHeap参数中元素个数每次减1,始终从位置0(堆顶)开始调整。

//heap sort public static void heapSort(int[] array, int n){ for (int i = n / 2 - 1; i >= 0; i--) buildHeap(array, n, i); int len = n - 1; while (len > 0) { swap(array, 0, len); buildHeap(array, len, 0); len--; } } private static void buildHeap(int[] array, int n, int i){ for (; left(i) < n; i = left(i)) { int bigger = right(i) < n ? max(array, left(i), right(i)) : left(i); if (array[bigger] > array[i]) //swap swap(array, bigger, i); else break; } } private static int left(int i){ return 2*i+1; } private static int right(int i){ return 2*i+2; } private static int max(int[] array, int i, int j){ return array[i]>array[j]? i:j; }

07

直接插入排序

插入排序算法,需要注意在移动排序区的元素时,会覆盖未排序区的第一个元素,所以需要先用另一个变量标记出来。

// insert sort public static void insertSort(int[] array, int n){ int i = 1; //unsorted first index while (i < n) { int j = i - 1; //sorted last index int insert = array[i]; //warning: label array[i] while (j > 0 && insert < array[j]){ array[j + 1] = array[j]; j--; } array[j + 1] = insert; //j+1 is insert pos i++; } }

08

希尔排序

希尔排序的精华是在插入排序的思想下多了一层分组逻辑,如下所示,d为分组长度,k为分组索引。内层逻辑实际上为插入排序的逻辑。

//shell Sort public static void shellSort(int[] array, int n, int group){ if (group > n) return; int d = n / group; //d: number for each group while (d > 0){ for (int i = 0; i < d; i++){ int j = i; // number index int k = 1; //distance index while (j < n){ int insert = array[j]; //label unsorted first j -= d; //sorted last index while (j > 0 && insert < array[j]){ array[j + d] = array[j]; j -= d; } array[j + d] = insert; //insert pos: j+d j = i + (++k) * d; //next number index } } d /= 2; } }

09

归并排序

二分后再归并是这个算法的精华所在,需要注意的是,递归排序的前半部分和后半部分各自的起始终止索引,以及归并时要分别指出array被分隔的两半部分的起始,终止位置,当然划分的前提是lo < hi,这也是递归返回的条件。

//merge sort public static void mergeSort(int[] array, int n){ var sorted = new int[n]; mergeSort(array,sorted,0,n-1); } private static void mergeSort(int[] array, int[] sorted, int lo, int hi){ if (lo < hi){ int mid = lo + (hi - lo) / 2; mergeSort(array, sorted,lo, mid); mergeSort(array, sorted, mid + 1, hi); merge(array, sorted, lo, mid, hi); } } //beg: part1 beginning index //mid: part1 end index //mid+1: part2 beginning index //end: part2 end index private static void merge(int[] array, int[] sorted, int beg, int mid, int end){ int i = beg; //part1 index int j = mid + 1; //part2 index int k = 0; //merged index while (i <= mid && j <= end) sorted[k++] = array[i] <= array[j] ? array[i++] : array[j++]; while (i <= mid) sorted[k++] = array[i++]; while (j <= end) sorted[k++] = array[j++]; for (i = 0; i < k; i++) array[beg + i] = sorted[i]; }

10

总结

对以上算法不清晰的地方请直接参考以下推送:

冒泡排序到快速排序做的那些优化

直接选择排序到堆排序做的那些改进

直接插入排序到希尔排序做的那些改进

归并排序算法的过程图解

不基于比较的基数排序原理图解

原文发布于微信公众号 - 算法channel(alg-channel)

原文发表时间:2017-11-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C/C++基础

打印1到最大的n位数

这道题是面试过可能会遇到的手写代码题。如n为3时,那么需要打印1到999。需要注意的是当输入的n很大时,最大的n位数是不能通过int或者long long in...

671
来自专栏编程之旅

唠唠快速排序算法

每一个从事计算机相关方向工作的同学一定听说过快速排序算法,在面试的准备过程中,快排也一定是一个必须要牢牢掌握的算法。那么今天就来唠唠快速排序算法。

1082
来自专栏计算机视觉与深度学习基础

Leetcode 287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 a...

2565
来自专栏技术之路

算法时间复杂度

     算法复杂度分为时间复杂度和空间复杂度,一个好的算法应该具体执行时间短,所需空间少的特点。      随着计算机硬件和软件的提升,一个算法的执行时间是算...

1856
来自专栏小樱的经验随笔

HUST 1586 数字排列

1586 - 数字排列 时间限制:1秒 内存限制:128兆 91 次提交 36 次通过 题目描述现有n个k位的数字,你的任务是重新安排数字每一位的位置,使得...

29912
来自专栏dalaoyang

递归基础思想

1703
来自专栏小二的折腾日记

牛客网刷题总结-剑指offer(1)

这里一般的思路肯定是,从行或者列开始找,根据递增的顺序,找到行或者列之后再判断列或者行,知道找到为止。最好的方法是,从左下角或者右上角开始找。原因是:这样的一行...

961
来自专栏ml

向前字典排序

          next_permutation算法对区间元素进行一次组合排序,使之字典顺序大于原来的排序,有如下两个使用原形,对迭代器区间[first,l...

2689
来自专栏Golang语言社区

Golang语言关于零值的定义

原文:https://golang.org/ref/spec#The_zero_value The 零值 当一个变量或者新值被创建时, 如果没有为其明确指定初始...

35911
来自专栏轮子工厂

设计模式(一) | 啥是工厂模式和策略模式?

752

扫码关注云+社区

领取腾讯云代金券