|
|
|||||
Сортировка массивов
Ишется алгоритм для ручной сортировки массивов.
Что имеется: var a1:Array = [12, 3, 1, 2, 2]; /*массив числовых данных типа int неопределенной длины, с разными/одинаковыми, неупорядоченными значениями*/ var a2:Array = ['a', 'b', 'c', 'd', 'e'] /*массив каких-либо объектов, в данном случае для удобства и наглядности они представлены в виде строковых данных, причем a1.length == a2.length;*/; Как бы Вы это реализовали правильно и красиво?
__________________
круглое тащим, квадратное катим |
|
|||||
...
модератор форума
Регистрация: Sep 2006
Адрес: Minsk
Сообщений: 4,286
|
Объединить числа из первого массива с соответствующими объектами из второго в одном объекте { index: 12, value: 'a' }, и сортировать по полю index.
|
|
|||||
Modus ponens
|
я бы добавил колбек в sort() первого массива и в нем бы сортировал второй... ну, скажем для коротких массивов это может быть не актуально, но для длинных - это ж нужно будет добавить целый массив фейк объектов которые нужны только для сортировки...
// 1, 2, 2, 3, 12 var a1:Array = [12, 3, 1, 2, 2]; // c, e, a, d, b var a2:Array = ["a", "b", "c", "d", "e"]; function numSort(a:int, b:int):int { var index:int; var s:String; if (a > b) { index = a1.indexOf(a); s = a2.splice(index, 1)[0]; a2.push(s); return 1; } else if (a < b) { return -1; } return 0; } a1.sort(numSort); trace(a2, a1); EDIT: Ой не... так не получится... сейчас посмотрел, там пары в каком-то странном порядке передаются и массив сам во время сортировки не меняется... вобщем, сорри, тогда только совй сот писать
__________________
Hell is the possibility of sanity Последний раз редактировалось wvxvw; 14.01.2010 в 21:10. |
|
|||||
Регистрация: Sep 2009
Сообщений: 18
|
Используйте любой стандартный алгоритм сортировки.
К примеру есть у вас QuickSort (Если не знаете, это такой быстрый алгоритм для сортировки (Сложность N*log N)) Взял на С++ что писал когда-то: Quick(int b, int e) { int i=b, j=e; int X = ar[(b+e) / 2]; // Здесь надо выбрать любой элемент массива. while (i<=j) { while (ar[i] < X) i++; while (ar[j] > X) j--; if (i<=j) { int tmp = ar[i]; ar[i] = ar[j]; ar[j] = tmp; i++; j--; } } if (i<e) Quick(i, e); if (b<j) Quick(b, j); } То есть вызывать функцию надо так: Quick(0, a1.length-1); // Если взять ваш пример Но вам нужно, насколько я понимаю, чтобы сохранились относительные позиции другого массива. Что ж, надо просто элементы другого массива менять аналогично первому, получим что-то вроде этого: (Type - тип элементов в другом массиве) Quick(int b, int e) { int i=b, j=e; int X = ar[(b+e) / 2]; // Здесь надо выбрать любой элемент массива. while (i<=j) { while (ar[i] < X) i++; while (ar[j] > X) j--; if (i<=j) { int tmp = ar[i]; ar[i] = ar[j]; ar[j] = tmp; Type tmp1 = ar1[i]; ar1[i] = ar1[j]; ar1[j] = tmp1; i++; j--; } } if (i<e) Quick(i, e); if (b<j) Quick(b, j); } |
|
|||||
[+1 19.06.10]
[+1 27.07.10] Регистрация: Aug 2009
Адрес: UTC+2
Сообщений: 353
|
скачайте книгу "СТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ
Bell Laboratories Муррей-Хилл, Нью-Джерси ДЖОН Э. ХОПКРОФТ ТЧОЯЛЧС Корнеллский университет Итака, Нью-Йорк ДЖЕФФРИ Д. УЛЬМАН Станфордский университет Стамфорд, Калифорния Она в русском переводе. Страница 228 - есть 100 методов сортировки с готовым кодом Будет очень красиво |
|
|||||
listener
|
Ну да, почему бы не реализовать вручную тот же пузырек? Просто двигать вместе с элементами а1 соответствующие элементы а2.
var a1:Array = [12, 3, 1, 2, 2]; /*массив числовых данных типа int неопределенной длины, с разными/одинаковыми, неупорядоченными значениями*/ var a2:Array = ['a', 'b', 'c', 'd', 'e']; /*массив каких-либо объектов, в данном случае для удобства и наглядности они представлены в виде строковых данных, причем a1.length == a2.length;*/ function sort(a1, a2) { var i:Number = 0; var j:Number = 0; var x:Number = 0; var s:String = ''; var size = a1.length; for (i = 0; i < size; i++) { for (j = size - 1; j > i; j--) { if (a1[j - 1] > a1[j]) { x = a1[j - 1]; s = a2[j - 1]; a1[j - 1] = a1[j]; a2[j - 1] = a2[j]; a1[j] = x; a2[j] = s; } } } } trace(a1);trace(a2); sort(a1, a2); trace(a1);trace(a2); Последний раз редактировалось alexcon314; 15.01.2010 в 11:40. |
|
|||||
Регистрация: Sep 2009
Сообщений: 18
|
Вот и я про тоже.. Только если элементов много, то он не прокатит..
|
|
|||||
Спасибо.
Пузырек вполне подходит и работает на ура. Только я вместо пишу:
__________________
круглое тащим, квадратное катим |
|
|||||
А чем плох Array.sortOn()? Или Vector.sort(myFunction)? В случае с вектором (FP 10 only) по идее будет даже быстрее, чем с Array... В обоих случаях имеется ввиду Object с полями index и value, как писал udaaff
__________________
...вселенская грусть |
Часовой пояс GMT +4, время: 23:26. |
|
« Предыдущая тема | Следующая тема » |
Опции темы | |
Опции просмотра | |
|
|