Algorithms

Insertion sort - сортировка вставками

Selection sort - сортировка выбором

Insertion sort - сортировка вставками

public static void insertIntoSort(int[] arr) {
    int temp, j;
    for(int i = 0; i < arr.length - 1; i++){
        if (arr[i] > arr[i + 1]) {
           temp = arr[i + 1];
           arr[i + 1] = arr[i];      
           j = i;
           while (j > 0 && temp < arr[j - 1]) {
               arr[j] = arr[j - 1];               
               j--;
           }
           arr[j] = temp;             
        }        
    }
}

Selection sort - сортировка выбором

Итерационный алгоритм:

public static void selectionSort (int[] numbers){
    int min, temp;

    for (int index = 0; index < numbers.length-1; index++){
        min = index;
        for (int scan = index+1; scan < numbers.length; scan++){
            if (numbers[scan] < numbers[min])
                min = scan;
        }

        // Swap the values
        temp = numbers[min];
        numbers[min] = numbers[index];
        numbers[index] = temp;
    }
}

Рекурсивный алгоритм:

public static int findMin(int[] array, int index){
    int min = index - 1;
    if(index < array.length - 1) min = findMin(array, index + 1);
    if(array[index] < array[min]) min = index;
    return min;
}

public static void selectionSort(int[] array){
    selectionSort(array, 0);
}

public static void selectionSort(int[] array, int left){
    if (left < array.length - 1) {
        swap(array, left, findMin(array, left));
        selectionSort(array, left+1);
    }
}

public static void swap(int[] array, int index1, int index2) {
    int temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
}

Merge sort - сортировка слиянием

private static int[] sortMerge(int[] arr) {
 int len = arr.length;
 if (len < 2) return arr;
 int middle = len / 2;
 return merge(sortMerge(Arrays.copyOfRange(arr, 0, middle)),
              sortMerge(Arrays.copyOfRange(arr, middle, len)));
}

Вверх