## ● 几种常见的排序算法，手写

### 参考回答：

function bubbleSort(data){
var temp=0;
for(var i=data.length;i>0;i--){
for(var j=0;j<i-1;j++){
if(data[j]>data[j+1])
{
temp=data[j];
data[j]=data[j+1];
data[j+1]=temp;
}
}
}
return data;
}

function selectionSort(data){
for(var i=0;i<data.length;i++){
var min=data[i];
var temp;
var index=1;
for(var j=i+1;j<data.length;j++){
if(data[j]<min)
{
temp=data[j];
data[j]=min;
min=temp;
}
}
temp=data[i];
data[i]=min;
data[index]=temp
}
}

function insertSort(data){
var len=data.length;
for(var i=0;i<len;i++){
var key=data[i];
var j=i-1;
while(j>=0&&data[j]>key){
data[j+1]=data[i];
j--;
}
data[j+1]=key;
}
return data;
}

function shallSort(array) {
var increment = array.length;
var i

var temp; //暂存

do {

//设置增量

increment = Math.floor(increment / 3) + 1;
for (i = increment ; i < array.length; i++) {
if ( array[i] < array[i - increment]) {
temp = array[i];
for (var j = i - increment; j >= 0 && temp < array[j]; j -= increment) {
array[j + increment] = array[j];
}
array[j + increment] = temp;
}
}
}
while (increment > 1)
return array;
}

function mergeSort ( array ) {
var len = array.length;
if( len < 2 ){
return array;
}
var middle = Math.floor(len / 2),
left = array.slice(0, middle),
right = array.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right)
{
var result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
return result;
}

function quickSort(arr){
if(arr.length==0)
return [];
var left=[];
var right=[];
var pivot=arr[0];
for(var i=0;i<arr.length;i++){
if(arr[i]<pivot){
left.push(arr[i]);
}
else{
right.push(arr[i]);
}
}
return quickSort(left).concat(pivot,quickSort(right));
}

## ● 数组的去重，尽可能写出多个方法

### 参考回答：

var array = ['1','2',1,'1','4','9','1'];
function unique(array){
var res=[];
for(var i=0,arraylen=array.length;i<array.length;i++){
for(var j=0,reslen=array.length;j<array.length;j++){
if(array[i]==res[j])
break;
}
if(j===reslen)
{
res.push(array[i])
}
}
return res;
}
console.log(unique(array));

2、用indexOf简化内层循环：indexOf函数返回某个指定的字符在字符串中第一次出现的位置

var array = ['1','2',1,'1','4','9','1'];
function unique(array){
var res=[];
for(var i=0,len=array.length;i<len;i++){
var current=array[i];
if(res.indexOf(current)===-1)
{
res.push(current);
}
}
return res;
}
console.log(unique(array));

var array = ['1','2',1,'1','4','9','1'];
function unique(array) {

// res用来存储结果

var res=[];
var sortArray = array.concat().sort();
console.log(sortArray);
var seen;
for(var i=0,len=sortArray.length;i<len;i++){
if(!i||seen!==sortArray[i]){
res.push(sortArray[i]);
}
seen=sortArray[i];
}
return res;
}
console.log(unique(array)); //

ES6的方法，使用set和map数据结构，以set为例，它类似于数组，但是成员的值都是唯一的，没有重复的值，很适合这个题目

var array = ['1','2',1,'1','4','4','1'];
function unique(array) {

// res用来存储结果

return Array.from(new Set(array));
}
console.log(unique(array));

var array = ['1','2',1,'1','4','4','1'];
function unique(array) {

// res用来存储结果

return [...new Set(array)];
}
console.log(unique(array));

## ● 给一个数，去一个已经排好序的数组中寻找这个数的位置（通过快速查找，二分查找）

### 参考回答：

function binarySearch(target,arr,start,end) {
var start   = start || 0;
var end     = end || arr.length-1;
var mid = parseInt(start+(end-start)/2);
if(target==arr[mid]){
return mid;
}else if(target>arr[mid]){
return binarySearch(target,arr,mid+1,end);
}else{
return binarySearch(target,arr,start,mid-1);
}
return -1;