简单的算法和排序

今天总结了下排序简单的算法

【自定义排序】
先寻找一个最小的数,然后依次那这个数和数组中其他数字比较,如果发现比这个数字小的数就把这两个数调换位置,然后再继续寻找下一个最小的数字进行下一轮比较

var arr = [31,6,19,8,2,3];
function findMin(start,arr){
var iMin = arr[start];
var iMinIndex = start;
for(var i = start+1;i<arr.length;i++){
if(arr[i]<iMin){
iMin = arr[i];
iMinIndex = i;
}
}
return iMinIndex;
}
function sort1(arr){

for(var i = 0;i<arr.length;i++){
var iMinIndex = findMin(i,arr);
var car;
car = arr[i];
arr[i] = arr[iMinIndex];
arr[iMinIndex] = car;
}
return arr;
}
document.write(sort1(arr));

【线性查找】:一个一个去查找

//不重复 有序
var arr = [0];
for(var i = 1;i<100000;i++){
arr[i] = arr[i-1]+Math.floor(Math.random()*4+1);
}

function find1(n,arr){
for(var i = 0;i<arr.length;i++){
if(arr[i]==n){
return true;
}
}
return false;
}
//测试性能
var t1 = new Date().getTime();
for(var i = 0;i<10000;i++){
var n = Math.random()*10000;
find2(n,0,arr.length-1)
}
alert(new Date().getTime()-t1);

【二分查找】:不停的分成两个部分,分部分查找
是一种万能方法,不一定是最好的,但是个保底的方法。(分治法)

***中间值 相加除以二,统一偏左,向下取整

//不重复 有序
var arr = [12,17,23,34,45,76,89];
function find2(n,s,e){
//边界处理
if(s>e){
return false;
}else if(s==e){
if(arr[s]==n){
return true;
}else{
return false;
}
}

var c = Math.floor((s+e)/2);
if(arr[c]==n){
return true;
}else{
if(n<arr[c]){
return find2(n,s,c);
}else{
return find2(n,c+1,e);
}

}
}

alert(find2(34,0,arr.length-1));//true false

【边界处理】-----递归,一层一层往下找

//要求数组不重复有顺序\
var arr=[12,23,34,45,56,67,78]
function find2(n,s,e){
if(s>e){
return fasle;
}else if(s==e){
if(arr[s]==e){
return true;
}else{
return false;
}
}
var c=Math.floor((s+e)/2);
if(arr[c]==n){
return true;
}else{
if(n<arr[c]){
return find2(n,s,c);
}else{
return find2(n,c+1,e);
}
}
}

alert(find2(12,arr.length+1,78));

应用

【查找最小值】

var arr = [12,54,32,9,5,3,1,101,-100,-1000];
function findMin(s,e){
if(s>e){
return [];
}else if(s==e){
return arr[s];
}else if(s == e-1){
if(arr[s]<arr[e]){
return arr[s];
}else{
return arr[e];
}
}
var c = Math.floor((s+e)/2);
var l = findMin(s,c);
var r = findMin(c+1,e);
if(l<r){
return l;
}else{
return r;
}
}
alert(findMin(0,arr.length-1));

【数组去重】

var arr = [1,2,3,4,5,4,3,4,5,2,1,4,2,1,5,7];
function findInArr(n,arr){
for(var i = 0;i<arr.length;i++){
if(arr[i]==n){
return true;
}
}
return false;
}
function removeCopy(s,e){
if(s>e){
return [];
}else if(s==e){
return [arr[s]];
}else if(s == e-1){
if(arr[s]==arr[e]){
return [arr[s]];
}else{
return [arr[s],arr[e]]
}
}
var c = Math.floor((s+e)/2);
var l = removeCopy(s,c);
var r = removeCopy(c+1,e);

for(var i = 0;i<r.length;i++){
if(!findInArr(r[i],l)){
l.push(r[i]);
}
}
return l;
}
document.write(removeCopy(0,arr.length-1));

【数组排序】

var arr = [34,32,1,76,55,-100,99,101];
function mySort(s,e){
//边界处理
if(s>e){
return [];
}else if(s==e){
return [arr[s]]
}else if(s == e-1){
if(arr[s]<arr[e]){
return [arr[s],arr[e]];
}else{
return [arr[e],arr[s]];
}

}
//1.切中间值
var c = Math.floor((s+e)/2);
//2.分半处理
var l = mySort(s,c);
var r = mySort(c+1,e);
var res = [];
while(l.length>0||r.length>0){
if(l[0]<r[0]){
res.push(l.shift());
}else{
res.push(r.shift());
}
}
if(l.length ==0){
res = res.concat(r);
}else if(r.length ==0){
res = res.concat(l);
}
return res;
}
//调用
document.write(mySort(0,arr.length-1));

冒泡排序 BubbleSort

循环,每次拿出两个值,两两比较,如果下一个值比目前的小,那么交换位置

外层循环是循环取数,内层循环是两两交换比较

var arr=[-122,-2,5,6,73,34,5,2];

function BubbleSort(arr){
for(var i=0;i<arr.length;i++){
for(var j=0;j<arr.length-1;j++){
if(arr[j]>arr[j+1]){
var tmp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=tmp
}
}
}
return arr;
}

document.write(BubbleSort(arr));

【快速排序】 -------quickSort

取数组中间的数,比中间数小的房中间数左边,比中间数大的放右边,再把两遍链接起来

function quickSort(arr,s,e){
//边界处理 参与流程
if(arr.length==0){
return [];
}

var c=Math.floor((s+e)/2);
var arrC=arr.splice(c,1);
var l=[];
var r=[];

for(var i=0; i<arr.length;i++){
if(arr[i]<arrC){
l.push(arr[i]);
}else{
r.push(arr[i]);
}
}
return quickSort(l).concat(arrC,quickSort(r));
}

var arr=[5,5,12,56,1,67,-1,-23-1];

document.write(quickSort(arr,0,arr.length-1));

【散列】 hash 哈希 数组 ------js常用用的结构
添加

var arr=[];
arr.length=0;
var cont=0;

function hash_add(n){

var pos=n%arr.length;
//当空间不足的时候

if(arr[pos]){
while(arr[pos]) {
cont++;
if(arr[pos]==n){
return;
}else{
pos++;
if(pos==arr.length){
pos=0;
}
}
}
arr[pos]=n;
}else{
arr[pos]=n;
}
//空间不足的时候的扩建
if(cont==arr.length){
//d等呗扩建
var oldArr=arr;
arr.length=oldArr.length*2;
arr=[];
for(var i=0;i<oldArr.length;i++){
arr.push(oldArr[i]);
count=0;
}
}
}

hash_add();

时间: 10-13

简单的算法和排序的相关文章

排序算法之 Java简单快速排序算法

package net.qh.test.sort; import java.util.ArrayList; import java.util.Calendar; import java.util.List; /** * Created by Administrator on 2016/03/01. */ public class SimpleQuick { public int[] sort(int[] arr,int left,int right){ if ( arr == null || a

数据结构杂谈(二)简单有趣的地精排序Gnome sort

很早之前便听说过地精排序的名字,今天自己看来一下,发现这是一种非常简单而且有趣的排序算法. 为什么叫地精排序? 地精排序在2000年由Dr. Hamid Sarbazi-Azad 提出的时候被称作 stupid sort,可见其思想的简单性.后来,这个算法被Dick Grune 描述成地精排序Gnome sort. 故事背景: Here is how a garden gnome sorts a line of flower pots.  Basically, he looks at the f

学习算法 -- 马桶排序、冒泡排序和快速排序

目录 马桶排序(令人作呕的排序) 冒泡排序(面试都要问的算法) 快速排序(见证亚当和夏娃的爱情之旅) 马桶排序(令人作呕的排序) 一.场景:期末考试完了,老师要将同学们的分数从高到低排序.假设班上有 5 名同学,分别考了 5 分.3 分.5 分.2 分和 8 分[满分:10 分],排序后的结果就是 8 5 5 3 2,现在,让我们先思考 10 分钟吧! 二.思路: (1)先创建一个数组 int scores[11],就有 scores[0]~scores[10] 共 11 个变量.我们用变量值为

[数据结构与算法]常用排序算法分析与实现:第一部分

声明:原创作品,转载时请注明文章来自SAP师太技术博客:www.cnblogs.com/jiangzhengjun,并以超链接形式标明文章原始出处,否则将追究法律责任!原文链接:http://www.cnblogs.com/jiangzhengjun/p/4289903.html 插入排序 直接插入排序.希尔排序 选择排序 简单选择排序.堆排序 交换排序 冒泡排序.快速排序 归并排序 基数排序 排序基类 1 package sort; 2 3 import java.util.Arrays; 4

经典排序算法 - 地精排序Gnome Sort

经典排序算法 - 地精排序Gnome Sort 号称最简单的排序算法,只有一层循环,默认情况下前进冒泡,一旦遇到冒泡的情况发生就往回冒,直到把这个数字放好为止 直接看它排序的过程,待排数组[6 2 4 1 5 9] 先设计一个标识i=0然后从头开始判断,什么时候(i < 6)不成立,什么时候排序结束, 所以,如何控制i的值是这个算法的关键 例如待排数组: [6 2 4 1 5 9] [0 1 2 3 4 5] 看一下具体的排序过程 [ i = 0 ]时啥也不干,先让i自增1,达到值为1才开始真正

线性排序算法---- 计数排序, 基数排序, 桶排序

排序算法里,除了比较排序算法(堆排序,归并排序,快速排序),还有一类经典的排序算法-------线性时间排序算法.听名字就让人兴奋! 线性时间排序,顾名思义,算法复杂度为线性时间O(n) , 非常快,比快速排序还要快的存在,简直逆天.下面我们来仔细看看三种逆天的线性排序算法, 计数排序,基数排序和桶排序. 1计数排序  counting Sort 计数排序 假设 n个 输入元素中的每一个都是在 0 到 k 区间内的一个整数,当 k= O(N) 时,排序运行的时间为 O(N). 计数排序的基本思想

简单的算法题, Find Minimum in Rotated Sorted Array 的Python实现。

简单的算法题, Find Minimum in Rotated Sorted Array 的Python实现. 题目: Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). Find the minimum element. You may assume no duplicate exists in t

【算法】排序(一)选择排序

在排序算法中,最简单的莫过于选择排序了. 排序思路: 在选择排序算法中分别有一个外循环和一个内循环,假设需要排序的序列共有n个元素,所以外循环的次数为n次,在n次交换(外循环)中,每次设置序列中的第一个元素为最小值(min),然后进行内循环,每次内循环都将序列中与min比较,若有元素小于min,则进行交换(若没有,min自己与自己交换).所以内循环的次数暂时不确定. 简而言之,就是在未排序的序列中,每次选取序列首位元素,依次与序列中其他元素比较,进而交换元素,达到排序的效果. 开始排序 1.外循

在Object-C中学习数据结构与算法之排序算法

笔者在学习数据结构与算法时,尝试着将排序算法以动画的形式呈现出来更加方便理解记忆,本文配合Demo 在Object-C中学习数据结构与算法之排序算法阅读更佳. 目录 选择排序 冒泡排序 插入排序 快速排序 双路快速排序 三路快速排序 堆排序 总结与收获 参考与阅读 选择排序 选择排序是一种简单直观的排序算法,无论什么数据进去都是 O(n2) 的时间复杂度.所以用到它的时候,数据规模越小越好.唯一的好处可能就是不占用额外的内存空间了吧. 1.算法步骤 首先在未排序序列中找到最小(大)元素,存放到排