Intereting Posts
Как декодировать / дешифровать MD5-шифрование с помощью Java Spring mvc найдено неоднозначное отображение. Невозможно сопоставить метод controllerа Написание переносимого Java-приложения с использованием JOGL и Android OpenGL Eclipse – целевой «неизвестный» в устройстве Android-устройства Ссылка на сценарий classа JavaFX Установка правильного PATH для Eclipse Проверка, является ли коллекция пустой в Java: что является лучшим методом? Как использовать POI SXSSF для чтения большой электронной таблицы java.lang.NoSuchFieldError: org.apache.http.message.BasicLineFormatter.INSTANCE от Mashape Unirest в приложении Java Является ли конкатенация пустой строкой, чтобы сделать преобразование строк действительно так плохо? Разница между Metaspace и Native Memory в Java Понимание собственных streamов java и jvm Отображение текущей даты с использованием тега JSTL formatDate Selenium: как запросить ввод пользователя и использовать входное значение? Weblogic медленно запускается (11 минут) под VM (VirtualBox и VMware)

Реализация двоичной вставки сортировки с использованием двоичного поиска в Java

У меня проблемы с объединением этих двух алгоритмов. Меня попросили изменить Binary Search чтобы вернуть индекс, который должен вставить элемент в массив. Затем меня попросили реализовать Binary Insertion Sort которая использует мой Binary Search для сортировки массива случайно генерируемых ints .

Мой Binary Search работает так, как он должен, возвращая правильный индекс, когда я тестирую его в одиночку. Я написал Binary Insertion Sort чтобы понять, как это работает, и получил это, чтобы работать. Как только я объединю их вместе, они ломаются. Я знаю, что я реализую их неправильно, но я не уверен, где моя проблема.

Вот что у меня есть:

 public class Assignment3 { public static void main(String[] args) { int[] binary = { 1, 7, 4, 9, 10, 2, 6, 12, 3, 8, 5 }; ModifiedBinaryInsertionSort(binary); } static int ModifiedBinarySearch(int[] theArray, int theElement) { int leftIndex = 0; int rightIndex = theArray.length - 1; int middleIndex = 0; while(leftIndex <= rightIndex) { middleIndex = (leftIndex + rightIndex) / 2; if (theElement == theArray[middleIndex]) return middleIndex; else if (theElement < theArray[middleIndex]) rightIndex = middleIndex - 1; else leftIndex = middleIndex + 1; } return middleIndex - 1; } static void ModifiedBinaryInsertionSort(int[] theArray) { int i = 0; int[] returnArray = new int[theArray.length + 1]; for(i = 0; i < theArray.length; i++) { returnArray[ModifiedBinarySearch(theArray, theArray[i])] = theArray[i]; } for(i = 0; i < theArray.length; i++) { System.out.print(returnArray[i] + " "); } } } 

Возвращаемое значение, которое я получаю для этого при запуске, равно 1 0 0 0 0 2 0 0 3 5 12 . Какие-либо предложения?

UPDATE: обновлено ModifiedBinaryInsertionSort

 static void ModifiedBinaryInsertionSort(int[] theArray) { int index = 0; int element = 0; int[] returnArray = new int[theArray.length]; for (int i = 1; i = 0 && theArray[index] > element) { theArray[index + 1] = theArray[index]; index = index - 1; } returnArray[index + 1] = element; } } 

Как работает сортировка вставки, он создает новый пустой массив B и для каждого элемента в несортированном массиве A он выполняет двоичный поиск в раздел B, который был построен до сих пор (слева направо), сдвигает все элементы на справа от местоположения в B, он выбирает один правый и вставляет элемент. Таким образом, вы создаете массив отсортированных по всему времени в B до тех пор, пока он не будет иметь полный размер B и не будет содержать все в A.

Две вещи:

Во-первых, двоичный поиск должен иметь возможность использовать int startOfArray и int endOfArray, и он будет бинарным поиском между этими двумя точками. Это позволяет вам рассматривать только часть массива B, которая на самом деле является отсортированным массивом.

Два перед установкой, вы должны переместить все элементы один вправо, прежде чем вставлять в зазор, который вы сделали.

Я понимаю, что это старо, но ответ на этот вопрос заключается в том, что, возможно, немного неинтуитивно, «Middleindex-1» не будет вашим индексом вставки во всех случаях. Если вы столкнетесь с несколькими делами на бумаге, проблема должна стать очевидной.

У меня есть метод расширения, который решает эту проблему. Чтобы применить его к вашей ситуации, вы будете проходить через существующий список, вставляя в пустой стартовый список.

 public static void BinaryInsert(this IList list, TItem item, Func sortfFunc) where TKey : IComparable { if (list == null) throw new ArgumentNullException("list"); int min = 0; int max = list.Count - 1; int index = 0; TKey insertKey = sortfFunc(item); while (min <= max) { index = (max + min) >> 1; TItem value = list[index]; TKey compKey = sortfFunc(value); int result = compKey.CompareTo(insertKey); if (result == 0) break; if (result > 0) max = index - 1; else min = index + 1; } if (index <= 0) index = 0; else if (index >= list.Count) index = list.Count; else if (sortfFunc(list[index]).CompareTo(insertKey) < 0) ++index; list.Insert(index, item); } 

Чувак, я думаю, у вас есть серьезные проблемы с вашим кодом. К сожалению, вам не хватает плода (логики) этого алгоритма. Ваша божественная цель здесь состоит в том, чтобы сначала получить индекс, вставка – это торт, но индекс нуждается в поту. Пожалуйста, не смотрите на этот алгоритм, если вы не отдали себя от этого и отчаялись. Никогда не сдавайтесь, вы уже знаете логику, ваша цель – найти ее в вас. Пожалуйста, дайте мне знать о любых ошибках, расхождениях и т. Д. Счастливое кодирование!

 public class Insertion { private int[] a; int n; int c; public Insertion() { a = new int[10]; n=0; } int find(int key) { int lowerbound = 0; int upperbound = n-1; while(true) { c = (lowerbound + upperbound)/2; if(n==0) return 0; if(lowerbound>=upperbound) { if(a[c]key && a[c-1]key) return c++; else { if(a[c]>key) upperbound = c-1; else lowerbound = c+1; } } } void insert(int key) { find(key); for(int k=n;k>c;k--) { a[k]=a[k-1]; } a[c]=key; n++; } void display() { for(int i=0;i<10;i++) { System.out.println(a[i]); } } public static void main(String[] args) { Insertion i=new Insertion(); i.insert(56); i.insert(1); i.insert(78); i.insert(3); i.insert(4); i.insert(200); i.insert(6); i.insert(7); i.insert(1000); i.insert(9); i.display(); } в public class Insertion { private int[] a; int n; int c; public Insertion() { a = new int[10]; n=0; } int find(int key) { int lowerbound = 0; int upperbound = n-1; while(true) { c = (lowerbound + upperbound)/2; if(n==0) return 0; if(lowerbound>=upperbound) { if(a[c]key && a[c-1]key) return c++; else { if(a[c]>key) upperbound = c-1; else lowerbound = c+1; } } } void insert(int key) { find(key); for(int k=n;k>c;k--) { a[k]=a[k-1]; } a[c]=key; n++; } void display() { for(int i=0;i<10;i++) { System.out.println(a[i]); } } public static void main(String[] args) { Insertion i=new Insertion(); i.insert(56); i.insert(1); i.insert(78); i.insert(3); i.insert(4); i.insert(200); i.insert(6); i.insert(7); i.insert(1000); i.insert(9); i.display(); } 

}

Вот мой метод для сортировки массива целых чисел с использованием двоичного поиска. Он изменяет массив, который передается как аргумент.

 public static void binaryInsertionSort(int[] a) { if (a.length < 2) return; for (int i = 1; i < a.length; i++) { int lowIndex = 0; int highIndex = i; int b = a[i]; //while loop for binary search while(lowIndex < highIndex) { int middle = lowIndex + (highIndex - lowIndex)/2; //avoid int overflow if (b >= a[middle]) { lowIndex = middle+1; } else { highIndex = middle; } } //replace elements of array System.arraycopy(a, lowIndex, a, lowIndex+1, i-lowIndex); a[lowIndex] = b; } }