структуры данных: быстрый список связанных списков с Java - PullRequest
Новая
       8

структуры данных: быстрый список связанных списков с Java

0 голосов
/ 16 ноября 2018

есть ли способ получить тот же результат при использовании LinkedList, а не массива?Следующий код работает отлично, только когда я использую массив в его обобщенной форме.Я хочу сделать то же самое с помощью LinkedList.вот как то так: 

public static <E extends Comparable<E>> LinkedList<E> qSort(LinkedList<E> list) {

    return list;
}

это то, что у меня уже есть .. 

 public static <E extends Comparable<E>> E[] quickSort(E[] list) {
    if (list.length <= 1) {
        return list;
    }
    sort(list, 0, list.length - 1);
    return list;
}

public static <E extends Comparable<E>> void sort(E[] list, int low, int high) {

    if ((high - low) <= 0) {
        return;
    }
    int splitPoint = split(list, low, high);
    sort(list, low, splitPoint - 1);
    sort(list, splitPoint + 1, high);
}

private static <E extends Comparable<E>> int split(E[] list, int low, int high) {
    int left = low + 1;
    int right = high;
    E pivot = list[low];
    while (left <= right) {
        if (list[left].compareTo(pivot) < 0) {
            left++;
        } else {
            break;
        }
    }
    while (true) {

        while (right > left) {
            if (list[right].compareTo(pivot) < 0) {
                break;
            } else {
                right--;
            }
        }

        if (left >= right) {
            break;
        }

        E temp = list[left];
        list[left] = list[right];
        list[right] = temp;
        left++;
        right--;
    }

    list[low] = list[left -1];
    list[left-1] = pivot;

    return left-1;
}
...