image.png
image.png
image.png
image.png
冒泡排序
// 测试用例类
var CArray = function(){
this.dataStore = [10,8,3,2,9,1];
this.swap = swap;
this.bubbleSort = bubbleSort;
}
// 交换方法
function swap(arr,index1,index2){
var temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
// 冒泡排序
function bubbleSort() {
var data = this.dataStore;
numEle = data.length;
for(var outer=numEle;outer>=2;--outer){
for(var inner=0;inner<=outer-1;inner++){
if(data[inner]>data[inner+1]){
this.swap(this.dataStore,inner,inner+1)
}
}
}
}
var mynums = new CArray();
mynums.bubbleSort(mynums);
console.log(mynums.dataStore);
选择排序
image.png
// 测试用例类
var CArray = function () {
this.dataStore = [1,8,3,2,9,5,4,7];
this.swap = swap;
this.selectSort = selectSort;
}
// 交换方法
function swap(arr,index1,index2){
var temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
// 选择排序方法
function selectSort() {
var min; // 注意
for(var outer = 0;outer<=this.dataStore.length-2;outer++){
min = outer;
for(var inner=outer+1;inner<this.dataStore.length;inner++){
if(this.dataStore[inner]<this.dataStore[min]){
min = inner;
}
}
// 找到最小值，进行交换
this.swap(this.dataStore,outer,min);
}
}
var mynums = new CArray();
mynums.selectSort();
console.log(mynums.dataStore);
插入排序
// 测试用例类
var CArray = function () {
this.dataStore = [1,8,3,2,9,5,4,7]
this.insertSort = insertSort;
}
// 插入排序方法
function insertSort() {
var temp,inner;
for(var outer=1;outer<this.dataStore.length;++outer){
temp = this.dataStore[outer];
inner = outer;
while(inner>0&&(this.dataStore[inner-1]>=temp)){
// 往后移动位置，让小元素移动到前面去
this.dataStore[inner] = this.dataStore[inner-1];
console.log('内部元素',this.dataStore);
inner--;
}
this.dataStore[inner] = temp; // 插入小元素
console.log('插入后的结果',this.dataStore);
}
}
var mynums = new CArray();
mynums.insertSort();
console.log(mynums.dataStore);
结果：
image.png
希尔排序
希尔排序是基于插入排序改进的，需要定间隔来进行每一次的排序
image.png
// 测试用例类
var CArray = function () {
this.dataStore = [10,8,3,2,5,9,4,7,35,48,20];
this.gaps = [5,3,1]; // 排序的间隔序列
this.shellSort = shellSort; // 静态希尔排序方法，间隔值是定死的
this.swap = swap; // 交换方法
this.dynamiSort = dynamiSort // 动态改变间隔值的希尔排序
}
// 交换方法
function swap(arr,index1,index2){
var temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
// 希尔排序
function shellSort() {
// 循环间隔序列
for(var g=0;g<this.gaps.length;g++){
// 拿到对应的间隔序列里面的元素
for(var i=this.gaps[g];i<this.dataStore.length;i++){
var temp = this.dataStore[i];
// 比较元素
for(var j=i;j>=this.gaps[g]&&this.dataStore[j-this.gaps[g]]>temp;j-=this.gaps[g]){
this.dataStore[j] = this.dataStore[j-this.gaps[g]];
}
this.dataStore[j] = temp;
}
console.log('输出间隔调换后的序列',this.dataStore);
}
}
// 动态改变间隔值的希尔排序
function dynamiSort() {
var N = this.dataStore.length;
var h = 1;
while(h<N/3){
h=3*h+1
}
while(h>=1){
for(var i=h;i<N;i++){
for(var j=i;j>=h&&this.dataStore[j]<this.dataStore[j-h];j=j-h){
this.swap(this.dataStore,j,j-h);
}
}
h = (h-1)/3;
}
}
var mynums = new CArray();
mynums.dynamiSort();
// console.log(mynums.dataStore);
console.log('动态希尔排序',mynums.dataStore);
归并排序
// 归并排序
function mergeSort(arr) {
if(arr.length<2){
return ;
}
var step = 1;
var left,right;
while(step<arr.length){
left = 0;
right = step;
while(right+step<=arr.length){
mergeArrays(arr,left,left+step,right,right+step);
left = right+step;
right = left+step;
}
if(right<arr.length){
mergeArrays(arr,left,left+step,right,arr.length);
}
step*=2;
}
}
// 合并数组方法
function mergeArrays(arr, startLeft, stopLeft, startRight, stopRight) {
var rightArr = new Array(stopRight-startRight+1);
var leftArr = new Array(stopLeft-startLeft+1);
k=startRight;
for(var i=0;i<(rightArr.length-1);i++){
rightArr[i] = arr[k]; // 拿到右数组
++k;
}
k=startLeft;
for(var i=0;i<(leftArr.length-1);i++){
leftArr[i] = arr[k]; // 拿到左数组
++k;
}
rightArr[rightArr.length-1] = Infinity;
leftArr[leftArr.length-1] = Infinity;
var m = 0; // 左数组开始位置
var n = 0; // 右数组的开始位置
for(var k=startLeft;k<stopRight;k++){
if(leftArr[m]<=rightArr[n]){
arr[k] = leftArr[m];
m++;
}else{
arr[k] = rightArr[n];
n++;
}
}
}
var arr = [23,45,19,98,32,67,12,3,9];
mergeSort(arr);
console.log(arr);
快速排序（重点）
// 快速排序
function qSort(list) {
if(list.length==0){
return [];
}
var pivot = list[0]; // 基准值
var lesser = []; // 小于的基准值
var greater = []; // 大于的基准值
for(var i=1;i<list.length;i++){
if(list[i]<pivot){
lesser.push(list[i]);
}else{
greater.push(list[i]);
}
}
return qSort(lesser).concat(pivot,qSort(greater)); // 不断的迭代
}
var data = [44,75,23,43,55,12,64,77,33];
console.log(qSort(data));
基准值:44当前元素:75
移动75到右边
基准值:44当前元素:23
移动23到左边
基准值:44当前元素:43
移动43到左边
基准值:44当前元素:55
移动55到右边
基准值:44当前元素:12
移动12到左边
基准值:44当前元素:64
移动64到右边
基准值:44当前元素:77
移动77到右边
基准值:44当前元素:33
移动33到左边
基准值:23当前元素:43
移动43到右边
基准值:23当前元素:12
移动12到左边
基准值:23当前元素:33
移动33到右边
基准值:43当前元素:33
移动33到左边
基准值:75当前元素:55
移动55到左边
基准值:75当前元素:64
移动64到左边
基准值:75当前元素:77
移动77到右边
基准值:55当前元素:64
移动64到右边
[ 12, 23, 33, 43, 44, 55, 64, 75, 77 ]
