почему быстрая сортировка не работает?

 
 
 
Сообщения:19
2 дня сижу над ней='( вроде бы правильный код. почему не работает? кто скажет???
public static int[] quickSort(int[] a) {
		int i = 0;
		int j = a.length - 1;
		int m = a[( a.length - 1 ) / 2];
		for ( ; ; ) {
			while ( a[i] <= m ) {
				if ( i >= j ) {
					break;
				}
				i ++;
			}
			while ( a[j] > m ) {
				if ( i >= j ) {
					break;
				}
				j --;
			}
			if ( i < j ) {
				swap ( a, i, j );
				i ++;
				j --;
			}
			else {
				if ( j > 0 ) {
					int[] a1 = quickSort(Arrays.copyOfRange(a, 0, j));
					System.arraycopy(a1, 0, a, 0, a1.length);
				}
				if ( i < a.length - 1 ) {
					int[] a2 = quickSort(Arrays.copyOfRange(a, i, a.length - 1));
					System.arraycopy(a2, 0, a, i, a2.length);
				}
				break;
			}
		}
		return a;
	}
	
	public static void swap( int[] a, int i, int j ) {
		int t = a[i];
		a[i] = a[j];
		a[j] = t;
		
	}

hi there
Изменен:05 дек 2019 03:05
 
 
Сообщения:1695
У вас не быстрая сортировка, вот с той же вики
- Выбрать из массива элемент, называемый опорным. Это может быть любой из элементов массива. От выбора опорного элемента не зависит корректность алгоритма, но в отдельных случаях может сильно зависеть его эффективность (см. ниже).
Тут у вас все соблюдается

-Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка, следующих друг за другом: «элементы меньшие опорного», «равные» и «большие»[1].
Тут у вас неверно, вы делаете swap всего 1 раз

-Для отрезков «меньших» и «больших» значений выполнить рекурсивно ту же последовательность операций, если длина отрезка больше единицы.
Тут вы тоже не следуете алгоритму, у вас нет рекурсии для каждого подотрезка
 
Модераторы:frymock
Сейчас эту тему просматривают:Нет