Как вставить сортировку? - PullRequest
Новая
       21

Как вставить сортировку?

0 голосов
/ 19 апреля 2020

Чего не хватает?

меньше, чуть-чуть Это почти сделано

Также есть ли способ сделать это быстрее? спасибо 

public class InsertionSort {
    public static void main(String[] argv) {
        int[] data = {4, 1, 7, 8, 9, 3, 2};
        sort(data);
        for (int i = 0; i < data.length; i++) {
            System.out.println(data[i]);
        }
    }
    public static void sort(int[] data) {
        int j, pivot;
        // insert data[i] to sorted array 0 ~ i - 1
        // begins from i = 1, because if the array has only one element then it must be sorted.
        for (int i = 1; i < data.length; i++) { 
            pivot = data[i];
            for (j = i - 1; j >= 0 && data[j] > pivot; j--)  // shift data[j] larger than pivot to right
            {               
                data[j+1] = data[j];
            }
        }
    }
}

1 Ответ

0 голосов
/ 19 апреля 2020

Ваш код имеет проблему при обмене значениями между данными [j + 1] и данными [j]. Вы перезаписываете значение из данных [j + 1], не сохраняя его во временной переменной и не помещая его в данные [j]. 

public class InsertionSort {
    public static void main(String[] argv) {
        int[] data = {4, 1, 7, 8, 9, 3, 2};
        sort(data);
        for (int i = 0; i < data.length; i++) {
            System.out.println(data[i]);
        }
    }

    public static void sort(int[] data) {
        int tmp, pivot;
        // insert data[i] to sorted array 0 ~ i - 1
        // begins from i = 1, because if the array has only one element then it must be sorted.
        for (int i = 1; i < data.length; i++) {
            pivot = data[i];
            for (int j = i - 1; j >= 0 && data[j] > pivot; j--)  // shift data[j] larger than pivot to right
            {
                tmp = data[j + 1];
                data[j + 1] = data[j];
                data[j] = tmp;
            }
        }
    }
}

Как подсказывает @ dan1st, попробуйте использовать быструю сортировку, если вы хотите повысить производительность. Хорошее объяснение алгоритма быстрой сортировки и его реализации Java вы можете найти здесь

...