ВАЖНО
- элементы всегда добавляются в конец структуры
- элементы всегда извлекаются из конца структуры
ПРИМЕР
стопка бумаги
- добавляем сверху
- забираем сверху
Рубрика: Структура Данных «Коллекция»
структура данных (тип, класс, даже лучше сказать интерфейс), которая создана, чтобы содержать в себе некоторое количество объектов (в зависимости от языка и терминологии они должны быть одного типа или могут быть разных типов).
Различные типы коллекций могут быть статическими или динамическими, т.е. изменять свой размер или оставаться постоянными, могут быть упорядоченными (точнее учитывающими порядок элементов) и неупорядоченными (соответственно не учитывающими).
O(log2n*n)
самый быстрый
разделяй и властвуй
делим массив на подмассивы и каждый раз рекурсивно
мы выбираем опорный элемент у каждого массива
его можно выбрать случайно, но часто центрально
пробегаемся по массиву и все элементы, которые меньше опорного, добавляем в один массив, все которые больше, добавляем в другой массив.
После такой операции у нас получается два массива
(с меньшими числами и с большими числами чем опорные).
Для каждого из этих массивов выполняется точно такая же операция. В каждой из этих массивов выбирается опорный элемент и происходит сортировка и так происходит до тех пор, пока длина массива становится равна единице (именно это условие и будет базовым случаем выхода из рекурсии).
И после этих операций эти маленькие массивы склеиваются в один большой.
const arr=[1,4,5,8,51,2,7,5,5,2,11]//[0,1,1,2,3....]
let cnt=0;
function quickSort(arr){
if (arr.length<=1){
return arr
}
let pivotIndex = Math.floor(arr.length/2);
let pivot=arr[pivotIndex]
let less=[]
let greater=[]
for(let i=0;i<arr.length;i++){
cnt+=1
if(i===pivotIndex)
continue;
if(arr[i]<pivot){
less.push(arr[i])
} else {
greater.push(arr[i])
}
return [...quickSort(less),pivot,...quickSort(greater)]
}
console.log(quickSort(arr))
console.log(cnt);O(n*n)
Не эффективная сортировка
- пробегаемся по всему массиву и сравниваем попарно лежащие элементы.
- Если следующий элемент массива меньше чем предыдущий, то мы меняем их местами и получается в своего рода всплытие — самый большой элемент потихоньку всплывает наверх
const arr=[1,4,5,8,51,2,7,5,5,2,11]//[0,1,1,2,3....]
let cnt=0;
function bubleSort(arr){
for (let i = 0; i< arr.length;i++){
for (let j = 0; j < arr.length; j++){
if(arr[j+1] < arr[j]){
let tmp = arr[j]
arr[j] = arr[j+1]
arr[j+1] = tmp
}
cnt+=1
}
}
return arr;
}
console.log('length',arr.length);
console.log(bubbleSort(arr))
console.log('count=',cnt)
O(k*n*n)=>O(n*n)
Процесс выполнения
есть массив не упорядоченных элементов
- мы в цикле находим минимальный элемент
- меняем местами найденный минимальный элемент с первым элементом
- опять ищем минимальный элемент и меняем уже со вторым элементом и так далее пока не будет отсортирован массив
const arr=[1,4,5,8,51,2,7,5,5,2,11]//[0,1,1,2,3....]
let cnt=0;
function selectionSort(arr){
for (let i = 0; i < arr.length; i++) {
let indexMin = i
for (let j=i+1; j < arr.length; j++){
if (arr[i] < arr[indexMin]){
indexMin=j
}
}
let tmp = arr[i];
arr[i]=arr[indexMin]
arr[indexMin]=tmp
}
}
console.log(selectionSort(arr))
console.log(arr.length)//))O(k*n*n)
console.log('count = ', count)O(log2n)
для массива из 1000 элементов
O(log21000)
время сортировки массива более длительнее чем работа линейного поиска
требование
массив отсортирован по порядку
Процесс выполнения
смотрим по середине символ
— если символ идет раньше, которую мы открыли, то будем
рассматривать левую часть
— если символ идет позже, которую мы открыли, то будем
рассматривать правую часть
таким образом каждый раз мы отсеиваем ровно половину в массиве пока не найдем элемент
количество итераций — счетчик выполнения оператора for
const arr=[1,4,5,8,51,2,7,5,5,2,11]
let cnt = 0;
function binarySearch(arr, item){
let start = 0
let end = arr.length;
let middle;
let found = false;
let position = -1;
while (found === false && start <= end){
cnt+=1
middle = Math.floor((start+end)/2);
if (arr[middle] === item){
found = true
position = middle
return position;
}
if (item < arr[middle]){
end = middle-1
} else {
start = middle+1
}
return position;
}
console.log(binarySearch(arr,0))
console.log(cnt);
- рекурсивный код более локаничный
cnt=0;
function recursiveBinarySearch(arr,item,start,end){
let middle = Math.floor((start+end)/2);
cnt+=1
if (item == arr[middle]){
return middle;
}
if (item < arr[middle]){
return recursiveBinarySearch(arr,item,start,middle-1)
} else {
return recursiveBinarySearch(arr,item,middle+1,end)
}
}
console.log(recursiveBinarySearch(arr,12,0,arr.length))
console.log(cnt);