排序
function CArray(numElements) {
this.dataStore = [];
this.pos = 0;
this.numElements = numElements;
this.insert = insert;
this.toString = toString;
this.clear = clear;
this.setData = setData;
this.bubbleSort = bubbleSort;
this.selectionSort = selectionSort;
this.insertionSort = insertionSort;
this.gaps = [5, 3, 1];
this.setGaps = setGaps;
this.shellsort = shellsort;
this.mergeSort = mergeSort;
this.mergeArrays = mergeArrays;
this.qSort = qSort;
this.getData = getData;
for (var i = 0; i < numElements; ++i) {
this.dataStore[i] = i;
}
}
function setData() {
for (var i = 0; i < this.numElements; i++) {
this.dataStore[i] = Math.floor(Math.random() * (this.numElements + 1))
}
//this.dataStore=[10,9,8,7,6,5,4,3,2,1]
}
function setGaps(arr) {
this.gaps = arr;
}
function getData() {
return this.dataStore;
}
function clear() {
for (var i = 0; i < this.dataStore.length; i++) {
this.dataStore[i] = 0;
}
}
function insert(element) {
this.dataStore[this.pos++] = element;
}
function toString() {
var restr = '';
for (var i = 0; i < this.dataStore.length; ++i) {
restr += this.dataStore[i] + ' ';
if (i > 0 && i % 10 == 0) {
restr += '\n';
}
}
return restr;
}
function swap(arr, index1, index2) {
var temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
//冒泡排序
//主要是有俩个循环，原理就是第一个数与第二个数进行比较，
//第一个循环是有多少个数需要进行比较，他就进行多少次循环，
//第二个循环就是有将这个数和所有的数进行比较，
function bubbleSort() {
var start = new Date().getTime()
var numElements = this.dataStore.length;
var temp;
//对于数组进行一个倒序的循环
for (var outer = numElements; outer >= 2; --outer) {
//inner是一个
for (var inner = 0; inner <= outer - 1; ++inner) {
if (this.dataStore[inner] > this.dataStore[inner + 1]) {
swap(this.dataStore, inner, inner + 1)
}
}
//console.log(outer+'次排序 : '+this.toString())
}
var stop = new Date().getTime();
console.log('冒泡排序计算时间：' + (stop - start) + '毫秒')
}
//选择排序
//将最小的的这个数放在第一位；
function selectionSort() {
var start = new Date().getTime()
var min, temp;
//第一次循环，有多少个数需要进行比较；
for (var outer = 0; outer < this.dataStore.length - 1; ++outer) {
//先对于位置进行缓存
min = outer;
//第二次循环位从后往前找，将数组中的第一个值与其他的所有的值进行比较；
for (var inner = outer + 1; inner <= this.dataStore.length - 1; ++inner) {
//如果第一个值是所有值值中最小的那么他就保持它的位置不变，
if (this.dataStore[inner] < this.dataStore[min]) {
min = inner;
}
swap(this.dataStore, outer, min);
}
// console.log(outer+'次排序 : '+this.toString())
}
var stop = new Date().getTime();
console.log('选择排序计算时间：' + (stop - start) + '毫秒')
}
//插入排序
function insertionSort() {
var start = new Date().getTime()
var temp, inner;//俩个缓存
//第一个循环是有多少个数值需要进行比较的；
for (var outer = 1; outer <= this.dataStore.length - 1; ++outer) {
temp = this.dataStore[outer];//将每一次的循环的数值进行缓存
inner = outer;//将位置进行缓存
//如果缓存的位置大于0；并且当前位置的前一位的值小于当前被位置的数值的才会进行一个循环
while (inner > 0 && (this.dataStore[inner - 1] >= temp)) {
//将当前位置的值等于前面的位置的值
this.dataStore[inner] = this.dataStore[inner - 1];
--inner;
}
// console.log(outer+'次排序 : '+this.toString())
//
this.dataStore[inner] = temp;
}
var stop = new Date().getTime();
console.log('插入排序计算时间：' + (stop - start) + '毫秒')
}
//希尔排序
function shellsort() {
var start = new Date().getTime()
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;
}
}
var stop = new Date().getTime();
console.log('希尔排序计算时间：' + (stop - start) + '毫秒')
}
//归并排序
function mergeSort() {
if (this.dataStore.length < 2) {
return;
}
var start = new Date().getTime()
var step = 1;
var left, right;
while (step < this.dataStore.length) {
left = 0;
right = step;
while (right + step <= this.dataStore.length) {
mergeArrays(this.dataStore, left, left + step, right, right + step);
left = right + step;
right = left + step;
}
if (right < this.dataStore.length) {
mergeArrays(this.dataStore, left, left + step, right, this.dataStore.length)
}
step *= 2;
}
var stop = new Date().getTime();
console.log('归并排序计算时间：' + (stop - start) + '毫秒')
}
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++;
}
}
}
a = 1;
//快速排序
function qSort(list) {
if (list.length == 0) {
return [];
}
var lesser = [];
var greater = [];
var pivot = list[0]
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 numElements = 10000000;
var myNums = new CArray(numElements)
myNums.setData()
var myNums1 = new CArray(numElements)
myNums1.setData()
var myNums2 = new CArray(numElements)
myNums2.setData()
var myNums3 = new CArray(numElements)
myNums3.setData()
// console.log(myNums3.getData())
// myNums3.mergeSort()
function Q(list) {
var start = new Date().getTime()
qSort(list)
var stop = new Date().getTime();
console.log('快速排序计算时间：' + (stop - start) + '毫秒')
}
// myNums.selectionSort()
// myNums1.insertionSort()
myNums2.shellsort()
Q(myNums3.getData())
