一.三种简单易懂的排序算法1.代码：packagecom.inspire.jdk.caculate;/***Createdbyyamingon18-6-26.*/publicclassOrderTest{publicstaticvoidmain(String[]args){/*冒泡排序:相邻两个位置元素比较,如果前面一个元素比后面一个元素大,就交换位置每一轮比较后,会确定一个最大值,最大值放在最后一位总共需要比较：data.length-1次下一轮比较的次数比上一轮比较的次数少一次时间复杂度：O(n^2).双重for循环*/int[]arr={2,4,5,3,9,1};for(inti=0;i<arr.length-1;i++){for(intj=0;j<arr.length-i-1;j++){if(arr[j]>arr[j+1]){intc=arr[j];arr[j]=arr[j+1];arr[j+1]=c;}}}/***选择排序：从数组中找到最小的元素,将它与数组第一个元素交换位置*没一次确定一个最小值,放在第一个位置*总共需要交换：data.length次*下一...

　　十种常见排序算法可以分为两大类：非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。 　　详情如下：　　　　　　　　　　　　　　排序算法的性能依赖于以下三个标准：稳定性：如果a原本在b前面，而a=b，排序之后a仍然在b的前面，则稳定；如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面，则不稳定。时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。 　　排序算法综合评估如下：　　　　　　　　　　　　　　冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列...

map是用来存放<key,value>键值对的数据结构，可以很方便快速的根据key查到相应的value。假如存储学生和其成绩（假定不存在重名，当然可以对重名加以区分），我们用map来进行存储就是个不错的选择。我们这样定义，map<string,int>，其中学生姓名用string类型，作为Key；该学生的成绩用int类型，作为value。这样一来，我们可以根据学生姓名快速的查找到他的成绩。       但是，我们除了希望能够查询某个学生的成绩，或许还想看看整体的情况。我们想把所有同学和他相应的成绩都输出来，并且按照我们想要的顺序进行输出：比如按照学生姓名的顺序进行输出，或者按照学生成绩的高低进行输出。换句话说，我们希望能够对map进行按Key排序或按Value排序，然后按序输出其键值对的内容。一、C++STL中Map的按Key排序      其实，为了实现快速查找，map内部本身就是按序存储的（比如红黑树）。在我们插入<key,...

排序算法经过了很长时间的演变，产生了很多种不同的方法。对于初学者来说，对它们进行整理便于理解记忆显得很重要。每种算法都有它特定的使用场合，很难通用。因此，我们很有必要对所有常见的排序算法进行归纳。    我不喜欢死记硬背，我更偏向于弄清来龙去脉，理解性地记忆。比如下面这张图，我们将围绕这张图来思考几个问题。    上面的这张图来自一个PPT。它概括了数据结构中的所有常见的排序算法。现在有以下几个问题：    1、每个算法的思想是什么？    2、每个算法的稳定性怎样？时间复杂度是多少？    3、在什么情况下，算法出现最好情况or最坏情况？    4、每种算法的具体实现又是怎样的？    这个是排序算法里面最基本，也是最常考的问题。下面是我的小结。一、直接插入排序(插入排序)。   ...

1.桶排序介绍桶排序(Bucketsort)是一种基于计数的排序算法，工作的原理是将数据分到有限数量的桶子里，然后每个桶再分别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）。当要被排序的数据内的数值是均匀分配的时候，桶排序时间复杂度为Θ(n)。桶排序不同于快速排序，并不是比较排序，不受到时间复杂度O(nlogn)下限的影响。桶排序按下面4步进行：1.设置固定数量的空桶。2.把数据放到对应的桶中。3.对每个不为空的桶中数据进行排序。4.拼接从不为空的桶中数据，得到结果。桶排序，主要适用于小范围整数数据，且独立均匀分布，可以计算的数据量很大，而且符合线性期望时间。2.桶排序算法演示举例来说，现在有一组数据[7,36,65,56,33,60,110,42,42,94,59,22,83,84,63,77,67,101]，怎么对其按从小到大顺序排序呢？操作步骤说明：1.设置桶的数量为5个空桶，找到最大值110，最小值7，每个桶的范围20.8=(110-7+1)/5。2.遍历原始数据，以链表结构，放到对应的桶中。数字7，桶索引值为0，计算公式为floor((7–7)/20.8...

编程论到极致，核心非代码，即思想。所以，真正的编程高手同时是思想独到及富有智慧（注意与聪明区别）的人。每一个算法都是一种智慧的凝聚或萃取，值得我们学习从而提高自己，开拓思路，更重要的是转换思维角度。其实，我们大多数人都活在“默认状态”下。没有发觉自己的独特可设置选项-----思想。言归正传（呵呵！恢复默认状态），以下学习基数排序。【1】基数排序以前研究的各种排序算法，都是通过比较数据大小的方法对欲排数据序列进行排序整理过程。而基数排序却不再相同，那么，基数排序是采用怎样的策略进行排序的呢？简略概述：基数排序是通过“分配”和“收集”过程来实现排序。而这个思想该如何理解呢？请看以下例子。（1）假设有欲排数据序列如下所示：73 22 93 43 55 14 28 65 39 81首先根据个位数的数值，在遍历数据时将它们各自分配到编号0至9的桶（个位数值与桶号一一对应）中。分配结果（逻辑想象）如下图所示：分配结束后。接下来将所有桶中所盛数据按照桶号由小到大（桶中由顶至底）依次重新收集串起来，得到如下仍然无...

计数排序的基本思想是：统计一个数序列中小于某个元素a的个数为n,则直接把该元素a放到第n+1个位置上。当然当过有几个元素相同时要做适当的调整，因为不能把所有的元素放到同一个位置上。计数排序假设输入的元素都是0到k之间的整数。//8-2.计数排序.cpp:定义控制台应用程序的入口点。//#include"stdafx.h"#include<iostream>usingnamespacestd;voidCountSort(inta[],intb[],intarray_size,intk){int*c=newint[k+1];for(inti=0;i<=k;i++){c[i]=0;}//c[i]containsthenumberofelementsequaltoifor(inti=0;i<array_size;i++){c[a[i]]++;}//c[i]containsthenumberofelementslessthanorequaltoifor(inti=1;i<=k;i++){c[i]=c[i]+c[i-1];}//confirmthenumpositio...

堆排序与快速排序，归并排序一样都是时间复杂度为O(N*logN)的几种常见排序方法。学习堆排序前，先讲解下什么是数据结构中的二叉堆。二叉堆的定义二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足二个特性：1．父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。2．每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。下图展示一个最小堆：由于其它几种堆（二项式堆，斐波纳契堆等）用的较少，一般将二叉堆就简称为堆。堆的存储一般都用数组来表示堆，i结点的父结点下标就为(i–1)/2。它的左右子结点下标分别为2*i+1和2*i+2。如第0个结点左右子结点下标分别为1和2。堆的操作——插入删除下面先给出《数据结构C++语言描述》中最小堆的建立插入删除的图解，再给出本人的实现代码，最好是先看明白图后再去看代码。堆的插入每次插入都是将新数据放在数组最后。可以发现从这个新数据的父结点到根结点必然为一个有序的数列，现在的任务是将这个新数据插入到这个有序数据中——这就类似...

归并排序基本思想：设两个有序的子序列(相当于输入序列)放在同一序列中相邻的位置上：array[low..m]，array[m+1..high]，先将它们合并到一个局部的暂存序列temp(相当于输出序列)中，待合并完成后将temp复制回array[low..high]中，从而完成排序。在具体的合并过程中，设置i，j和p三个指针，其初值分别指向这三个记录区的起始位置。合并时依次比较array[i]和array[j]的关键字，取关键字较小（或较大）的记录复制到temp[p]中，然后将被复制记录的指针i或j加1，以及指向复制位置的指针p加1。重复这一过程直至两个输入的子序列有一个已全部复制完毕(不妨称其为空)，此时将另一非空的子序列中剩余记录依次复制到array中即可。合并已排序的序列的具体实现代码：voidmergearray(inta[],intfirst,intmid,intlast,inttemp[]){inti=first,j=mid+1;intm=mid,n=last;intk=0;while(i<=m&&j<=n){if(a[i]<=a[j]){...

一.算法描述   插入排序：插入即表示将一个新的数据插入到一个有序数组中，并继续保持有序。例如有一个长度为N的无序数组，进行N-1次的插入即能完成排序；第一次，数组第1个数认为是有序的数组，将数组第二个元素插入仅有1个有序的数组中；第二次，数组前两个元素组成有序的数组，将数组第三个元素插入由两个元素构成的有序数组中......第N-1次，数组前N-1个元素组成有序的数组，将数组的第N个元素插入由N-1个元素构成的有序数组中，则完成了整个插入排序。二.来自算法导论的算法伪代码：insert_sort(A):forj<——1tolength[A]-1dokey<——A[j]//insertA[j]intothesortedsequenceA[1...j-1]i<——j-1whilei>=0andA[i]>keydoA[i+1]=A[i]i<——i-1A[i+1]<——key三.简单算法实现#include<stdio.h>voidinsert_sort(int*arr,intn){assert(n>0...

快速排序的第一种实现（单指针移动，挖空填数）快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想----分治法也确实实用，因此很多软件公司的笔试面试，包括像腾讯，微软等知名IT公司都喜欢考这个，还有大大小的程序方面的考试如软考，考研中也常常出现快速排序的身影。总的说来，要直接默写出快速排序还是有一定难度的，因为本人就自己的理解对快速排序作了下白话解释，希望对大家理解有帮助，达到快速排序，快速搞定。 快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。该方法的基本思想是：1．先从数列中取出一个数作为基准数。2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。3．再对左右区间重复第二步，直到各区间只有一个数。 虽然快速排序称为分治法，但分治法这三个字显然无法很好的概括快速排序的全部步骤。因此我的对快速排序作了进一步的说明：挖坑填数+分治法：先来看实例吧，定义下面再给出（最好能用自己的话...

1、三路快速排序算法的基本思想之前的快速排序算法都是将序列分成<=v和>v或者是<v和>=v的两个部分，而三路快速排序是将序列分成三个部分:<v、=v、>v，如下图所示:  首先v元素还是作为"基准"元素，e表示当前遍历索引值指向的元素，也就是待考虑的元素，从图中可以看出来，整个序列被分成3个部分，也就是说当我们遍历完成之后整个序列就已经被分成了<v、=v、>v三个部分了，而我们只需要对<v和>v的两个部分再次递归调用三路排序函数进行排序即可，来看看具体的过程:  首先来看看整个序列的布局，这里我们使用了3个索引值来表示3个不同的位置，使用lt索引来表示<v部分和=v部分的分界处（这里选的是<v部分的最后一个元素），使用i索引表示遍历的位置，使用gt索引来表示=v部分和>v部分的分界处（这里选的是>v部分的第一个元素）。  如果当前i指向的元素=v，那直接就将此元素归为=v部分，i++即可  如果当前i指向的元素<v，...

1、算法出现的背景之前讲的，当我们排序的是一个近乎有序的序列时，快速排序会退化到一个O(n^2)级别的排序算法，而对此的改进就是引入了随机化快速排序算法；但是当我们排序的是一个数值重复率非常高的序列时，此时随机化快速排序算法就不再起作用了，而将会再次退化为一个O(n^2)级别的排序算法，那为什么会出现这种情况呢？且听下面的分析: 如上图所示就是之前分析的快速排序算法的partition的操作原理，我们通过判断此时i索引指向的数组元素e>v还是<v，将他放在橙色或者是紫色两个不同的位置，然后将整个数组分成两个部分递归下去；但是这里其实我们是没有考虑=v的情况，其实隐含的意思就是下面的两种情况:      其实从这里就可以看出来了，不管是>=v还是<=v，当我们的序列中存在大量重复的元素时，排序完成之后就会将整个数组序列分成两个极度不平衡的部分，所以又退化到了O(n^2)级别的时间复杂度，这是因为对于每一个"基准"元素来说，重复的元素太多了，如果我们选的"基准"元素稍微有一点的不平衡，那么就会导致...

1、什么是自底向上的归并排序？说到底，不管是前面说的自顶向下的归并排序还是现在讲的自底向上的归并排序，其实质都是归并。来看看一个演示过程: 这个就是待排序的数组序列  先将数组序列以2个元素为一组分成4组，每个组内部分成2个子序列进行向上合并  这是合并之后的效果  然后以4个元素为一组分成2组，每个组内部分成2个子序列进行向上合并  这是合并之后的效果  然后以8个元素为一组分成1个组，每个组内部分成2个子序列进行向上合并  最终整个序列编程有序的了其实从这里看就可以知道，这个就好像是前面说的自顶向下排序过程中的后面一个过程。 2、时间复杂度同自顶向下的归并排序相同，时间复杂度也是O(nlogn)级别。 3、算法的实现（基于C++）#define MIN(a,b) ((a)<(b)?(a):(b))1/*****************************自底向上的归并排序算法实现*************...

1、什么是归并排序？归并排序是利用递归和分而治之的技术将数据序列划分成为越来越小的序列，将两个（或两个以上）有序子序列合并成一个新的有序序列，即把待排序序列分为若干个子序列，每个子序列是有序的，然后再把有序子序列合并为一个新的有序序列，最终将整个序列变得有序。时间复杂度:O(nlogn) 2、效果演示 这个序列为待排序序列  将这个序列分成2个子序列，分别对它们进行排序，再合并为一个新的有序序列  同理在对上面的两个子序列排序的时候，也会将他们各自分为2个子序列，分别                      对它们进行排序，再合并   继续沿用上面的思想，再对它们进行分半，此时每一个子序列只有一个元素了，      &n...