数据结构与算法JavaScript描述练习------第13章检索算法
1. 顺序查找算法总是查找数据集中匹配到的第一个元素。请重写该算法使之返回匹配到的 最后一个元素。
function seqSearchLast(arr, data) {
var lastIndex = -1;
for (var i = 0; i < arr.length; i++) {
if (arr[i] == data) {
lastIndex = i;
}
}
return lastIndex;
}
function dispArr(arr) {
for (var i = 0; i < arr.length; ++i) {
console.log(arr[i] + " ");
if (i % 10 == 9) {
console.log("\n");
}
}
if (i % 10 != 0) {
console.log("\n");
}
}
var nums = [];
for (var i = 0; i < 10; ++i) {
nums[i] = Math.floor(Math.random() * 11);
}
dispArr(nums);
var readline = prompt("输入一个要查找的数字：");
var num = parseInt(readline);
var lastIndex = seqSearchLast(nums, num);
if (lastIndex !== -1) {
console.log(num + " 最后出现在数组中的位置是：" + lastIndex);
} else {
console.log(num + " 没有出现在这个数组中。");
}2. 对同一个数据集进行测试，比较顺序查找算法执行所花费的时间与同时使用插入排序算 法和二分查找算法花费的总时间。你得到的结果是什么？
function seqSearch(arr, data) {
for (var i = 0; i < arr.length; ++i) {
if (arr[i] == data) {
return i;
}
}
return -1;
}
function findMin(arr) {
var min = arr[0];
for (var i = 1; i < arr.length; ++i) {
if (arr[i] < min) {
min = arr[i];
}
}
return min;
}
function findMax(arr) {
var max = arr[0];
for (var i = 1; i < arr.length; ++i) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
function swap(arr, index, index1) {
temp = arr[index];
arr[index] = arr[index1];
arr[index1] = temp;
}
function seqSearch1(arr, data) {
for (var i = 0; i < arr.length; ++i) {
if (arr[i] == data && i > (arr.length * 0.2)) {
swap(arr, i, 0);
return true;
} else if (arr[i] == data) {
return true;
}
}
return false;
}
function insertionsort(arr) {
var temp, inner;
for (var outer = 1; outer <= arr.length-1; ++outer) {
temp = arr[outer];
inner = outer;
while (inner > 0 && (arr[inner-1] >= temp)) {
arr[inner] = arr[inner-1];
--inner;
}
arr[inner] = temp;
}
}
function binSearch(arr, data) {
var upperBound = arr.length-1;
var lowerBound = 0;
while (lowerBound <= upperBound) {
var mid = Math.floor((upperBound + lowerBound) / 2);
if (arr[mid] < data) {
lowerBound = mid + 1;
} else if (arr[mid] > data) {
upperBound = mid - 1;
} else {
return mid;
}
}
return -1;
}
function count(arr, data) {
var count = 0;
var position = binSearch(arr, data);
if (position > -1) {
++count;
for (var i = position-1; i > 0; --i) {
if (arr[i] == data) {
++count;
} else {
break;
}
}
for (var i = position+1; i < arr.length; ++i) {
if (arr[i] == data) {
++count;
} else {
break;
}
}
}
return count;
}
function generateRandomArray(size, maxVal) {
let arr = [];
for (let i = 0; i < size; ++i) {
arr.push(Math.floor(Math.random() * maxVal));
}
return arr;
}
function testSequentialSearch(arr, data) {
let startTime = performance.now();
seqSearch(arr, data);
let endTime = performance.now();
return endTime - startTime;
}
function testInsertionSortAndBinarySearch(arr, data) {
let startTime = performance.now();
insertionsort(arr);
let sortTime = performance.now() - startTime;
startTime = performance.now();
binSearch(arr, data);
let searchTime = performance.now() - startTime;
return sortTime + searchTime;
}
function main() {
const size = 10000;
const maxVal = 100000;
const data = Math.floor(Math.random() * maxVal);
let arr = generateRandomArray(size, maxVal);
console.log("Sequential Search Time:", testSequentialSearch(arr.slice(), data), "ms");
console.log("Insertion Sort + Binary Search Time:", testInsertionSortAndBinarySearch(arr.slice(), data), "ms");
}
main();
//Sequential Search Time: 0.4 ms
//Insertion Sort + Binary Search Time: 26.4ms3. 创建一个函数用来查找数据集中的次小元素。你能否归纳一下，如何实现查找第三小、 第四小，等等的搜索函数？在至少有 1000 个元素的数据集上测试你的函数。请同时在 数字和文本数据集上进行测试。
function seqSearch(arr, data) {
for (var i = 0; i < arr.length; ++i) {
if (arr[i] == data) {
return i;
}
}
return -1;
}
function findMin(arr) {
var min = arr[0];
for (var i = 1; i < arr.length; ++i) {
if (arr[i] < min) {
min = arr[i];
}
}
return min;
}
function findMax(arr) {
var max = arr[0];
for (var i = 1; i < arr.length; ++i) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
function swap(arr, index, index1) {
temp = arr[index];
arr[index] = arr[index1];
arr[index1] = temp;
}
function seqSearch1(arr, data) {
for (var i = 0; i < arr.length; ++i) {
if (arr[i] == data && i > (arr.length * 0.2)) {
swap(arr, i, 0);
return true;
} else if (arr[i] == data) {
return true;
}
}
return false;
}
function insertionsort(arr) {
var temp, inner;
for (var outer = 1; outer <= arr.length-1; ++outer) {
temp = arr[outer];
inner = outer;
while (inner > 0 && (arr[inner-1] >= temp)) {
arr[inner] = arr[inner-1];
--inner;
}
arr[inner] = temp;
}
}
function binSearch(arr, data) {
var upperBound = arr.length-1;
var lowerBound = 0;
while (lowerBound <= upperBound) {
var mid = Math.floor((upperBound + lowerBound) / 2);
if (arr[mid] < data) {
lowerBound = mid + 1;
} else if (arr[mid] > data) {
upperBound = mid - 1;
} else {
return mid;
}
}
return -1;
}
function count(arr, data) {
var count = 0;
var position = binSearch(arr, data);
if (position > -1) {
++count;
for (var i = position-1; i > 0; --i) {
if (arr[i] == data) {
++count;
} else {
break;
}
}
for (var i = position+1; i < arr.length; ++i) {
if (arr[i] == data) {
++count;
} else {
break;
}
}
}
return count;
}
function ensureAllStrings(arr) {
return arr.map(item => String(item));
}
function findSecondSmallest(arr) {
if (arr.length < 2) {
throw new Error('Array must have at least two elements');
}
const uniqueElements = Array.from(new Set(arr));
if (uniqueElements.length < 2) {
throw new Error('Array must have at least two unique elements');
}
const sortedUniqueElements = ensureAllStrings(uniqueElements).sort((a, b) => a.localeCompare(b));
return sortedUniqueElements[1];
}
function findKthSmallest(arr, k) {
if (k < 1 || k > arr.length) {
throw new Error('Invalid k value');
}
const uniqueElements = Array.from(new Set(arr));
if (k > uniqueElements.length) {
throw new Error('k is larger than the number of unique elements');
}
const sortedUniqueElements = ensureAllStrings(uniqueElements).sort((a, b) => a.localeCompare(b));
return sortedUniqueElements[k - 1];
}
function filterEmptyStrings(arr) {
return arr.filter(str => str !== '');
}
function generateRandomArray(size, maxVal) {
var arr = [];
for (var i = 0; i < size; ++i) {
arr.push(Math.floor(Math.random() * maxVal));
}
return arr;
}
function testFindKthSmallest() {
var size = 1000;
var maxVal = 10000;
var arr = generateRandomArray(size, maxVal);
console.log("Generated array:", arr);
console.log("Second smallest element:", findSecondSmallest(arr));
console.log("Third smallest element:", findKthSmallest(arr, 3));
console.log("Fourth smallest element:", findKthSmallest(arr, 4));
}
testFindKthSmallest();
function generateRandomTextArray(size, maxLength) {
var arr = [];
var characters = 'abcdefghijklmnopqrstuvwxyz';
for (var i = 0; i < size; ++i) {
var text = '';
for (var j = 0; j < Math.floor(Math.random() * maxLength); ++j) {
text += characters[Math.floor(Math.random() * characters.length)];
}
arr.push(text);
}
return arr;
}
function testFindKthSmallestText() {
var size = 1000;
var maxLength = 10;
var arr = generateRandomTextArray(size, maxLength);
console.log("Generated text array:", arr);
var filteredArr = filterEmptyStrings(arr);
console.log("Second smallest element:", findSecondSmallest(filteredArr));
console.log("Third smallest element:", findKthSmallest(filteredArr, 3));
console.log("Fourth smallest element:", findKthSmallest(filteredArr, 4));
}
testFindKthSmallestText();