冒泡排序：思想： 冒泡排序重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说排序完成特点：比较稳定，排序数较小是比较好package cn.guangboyuan;/*** @author Red Ants* 微信公众号：程序员之路* 两种冒泡排序的性能比较*/publicclass DubbleSort {privatestaticboolean checkArray(int[] data){if(data == null || data.lengt...
1. 冒泡排序var arr = array(10, 20, 45, 71, 98); for（i = 0 ; i < arr.length ; i++）{ for (j = 0 ; j < arr.length-1-i ; j++) { if(arr[j] < arr[j+1]) { var tmp = arr[j]; arr[j] = arr [j+1]; arr[j+1] = tmp; } } ruturn arr;} 原文：https://www.cnblogs.com/fanshehu/p/11962637.html
单向链表： 最好情况：头节点 O(1)最坏情况：尾节点 O(n) 双向链表： 最好情况：insert/delete 头节点/尾节点 O(1)最坏情况：元素不在数组中，遍历所有元素 O(n) 数组擅长读取，链表擅长写入。写入要先读取定位，再写入。读取场景： 任意序位读取，复杂度： 数组O(1)，链表O(n)。 写入场景： 任意序位写入，定位复杂度：数组O(1)，链表O(n)；写入复杂度：数组O(n)，链表O(1)。 为什么数组的插入的复杂度是O(1)? 在数组尾部插入...
题意：两地之间有n条不相交路径，第i条路径由a[i]座桥组成，每座桥有一个损坏概率，让你确定一个对所有桥的检测顺序，使得检测所需的总期望次数最小。首先，显然检测的时候，是一条路径一条路径地检测，跳跃地检测没有意义。考虑已经排好的某个路径的顺序，相邻的两条路径j和j+1如果满足：(route[j].A+route[j].B)+(route[j+1].A+route[j+1].B)*(1.0-route[j].c)> (route[j].A+route[j].B)*(1.0-route[j+1].c)+(route[j+1].A+rou...
归并排序里运用到算法里很重要的一个思想——分治法：将原问题分解为几个规模较小但类似于原问题的子问题——《算法导论》。在每一层递归中都有3个步骤： 1.分解问题 2.解决问题 3.合并问题的解 举例待排序数组：{6, 5, 3, 1, 7, 2, 4}，将它原始序列做分解。 可以经过不断的递归分解可以看到已经把原始数组序列不断分解为最小单位，接下来不妨将它们看做是二叉树的叶子节点。 将他们进行两两归并排序形成二叉树...
结论：由于计数排序不是基于比较的排序，所以时间复杂度可以突破O(nlgn);计数排序时间复杂度为O(n),额外空间复杂度为O(n);Java实现代码如下： 1package com.cmbc.test1;2 3publicclass CountSorting {4 5publicstaticvoid countSort(int[] arr){6if(arr==null||arr.length<2){7return;8 }9int max = Integer.MIN_VALUE; 10for(int i = 0 ;i<arr.length;i++){ 11 max = Math.max(max, arr[i]); 12 } 13in...
在C++的泛型排序中，拷贝对象需要很大的开销，而比较对象常常是相对省时的（编译器的自动优化）。在这种情况下，如果我们能够使用更少的数据移动，那么有理由让一个算法多使用一些比较。而快速排序（Quicksort）满足了这种特点，实际上C++中通常所使用的排序例程就是使用的快速排序。 快速排序也是一种分治的递归算法。它的平均运行时间是O(NlogN)，最坏情形性能为O(N2)。将数组S排序的基本算法由下列简单的四步组成：如果S中元素个...
算法思想1，申请空间，使其大小为2个已经排序的数列之和，该空间用来存放合并后的序列。2，设定2个指针，最初位置为2个已经排序数列的的起始位置。3，比较2个指针所指向的元素，选择较小的元素放入合并空间，并移动指针到下个位置。4，重复步骤3，知道某一个指针到达数列尾部。5，将另一个数列的剩余元素全部复制到合并空间。归并排序原理归并排序具体工作原理如下（假设序列共有n个元素）：将序列每相邻两个数字进行归并操作，形成...
import cn.idestiny.util.GeneratedArray;/*** @Auther: FAN* @Date: 2018/8/25 20:11* @Description:选择排序 每次排序选择出最小的数字放在对应位置* 1） 3，5，1，2 最小值 1 和3交换* 2） 1，5，3，2 最小值 2 和5交换* 3） 1，2，3，5 排序完成**/publicclass SelectionSort {publicstaticvoid main(String[] args) {int[] arr = GeneratedArray.randomGeneratedArray(10, 50, 10000);long start = System.currentTimeMillis(...
#!/usr/bin/env python#coding:utf-8import types,sys# 简单的排序l=[1,9,2,3,-1,724,219,888]for i in range(len(l)): for j in range(i,len(l)): if l[j] > l[i]: l[i],l[j]=l[j],l[i]print l# 定义为函数并加入判断的排序def sort(list_sort): if type(list_sort) == types.ListType: # 判断输入的是否为列表 if len(list_sort)==0: # 判断列表长度 ...
http://blog.csdn.net/it_zjyang/article/details/53406764http://blog.csdn.net/hacker00011000/article/details/52176100尾递归：https://www.cnblogs.com/babybluevino/p/3714022.html迭代，循环，遍历，递归的区别：https://www.cnblogs.com/feichengwulai/articles/3642107.html递归的效率：http://www.nowamagic.net/librarys/veda/detail/2321 原理快速排序使用分治的思想，通过一趟排序将待排序列分割成两部分，其中一部分...
算法参考：快速排序(三种算法实现和非递归实现) 上面这篇文章对快排讲解得不错。快排概念详述请点上面链接。记录一下，用lua实现的快排，以及一些注意的地方。 交换函数：function Swap(tab, i, j)local temp = tab[i];tab[i] = tab[j];tab[j] = temp; end一、左右指针法：-- 左右指针法 -- 最后一个数为枢轴function PartSort(tab, left, right)local key = right;while left < right do-- 必须先由左向右遍历while left < right ...
什么是插入排序？ 同样，插入排序会涉及到两个区域：有序区域。有序区域内的元素，元素从小到大分布（或者从大到小分布）。在开始排序之前有序区域为第一个元素。无序区域。无序区域内的元素，元素任意分布，在开始排序之前除了第一个元素之外的所有元素都处在无序区域内。 插入排序，在无序区域内根据顺序取出每一个元素X。在有序区域内从后往前寻找合适元素X的位置，保证插入后，元素X与有序区域内的其他元素依然组成有序区域。 ...
//插入排序//C++#include <iostream>using namespace std; void main(){ int a[6]={5,2,4,6,1,3};//定义一个未排好序的数组 int i,j,key; for(i=0;i<6;i++)//输出排序前的序列 printf("%3d",a[i]); for(j=1;j<6;j++) { key=a[j]; i=j-1; while(i>=0&&a[i]>key) { a[i+1]=a[i]; i=i-1; } a[i+1]=key; } cout<<endl; for(i=0;i<6;i++)//...
? 好程序员Java学习路线分享冒泡排序及优化，冒泡排序是一定典型的交换排序，如排序规则是升序，有如下数列： ? A[0] A[1] A[2] A[3] ...... A[n]? 将A[0]和A[1]比较，如果A[0]>A[1] ，则交换两个元素的位置，否则不变， 再继续比较A[1]和A[2]，直到A[n-1]和A[n]。即比较相邻的两个元素，如果前一个大，就交换（否则不交换），再继续比较后面的元素，每一轮比较之后，最大的元素会移动到最后（完成一轮冒泡）；再开始第二轮冒泡，本...