从零开始的算法练习2

冒泡排序

public class BubbleSort {

    public static void bubbleSort(int[] arr) {
        for (int i = arr.length; i > 1; i--) {
            boolean ifSwap = false;
            for (int j = 1; j < i; j++) {
                if (arr[j - 1] > arr[j]) {
                    swap(arr, j - 1, j);
                    ifSwap = true;
                }
            }
            System.out.println(ifSwap);
            System.out.println(Arrays.toString(arr));
            if(!ifSwap) break;
        }
    }

    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {15, 4, 5, 2, 7, 12, 6, 1, 4, 3, 9, 8, 4, 4, 4, 10};
        bubbleSort(arr);
    }
}

选择排序

public class SelectionSort {

    public static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if(arr[j]<arr[min]){
                    min = j;
                }
            }
            swap(arr, i, min);
            System.out.println(Arrays.toString(arr));
        }
    }

    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {15, 4, 5, 2, 7, 12, 6, 1, 4, 3, 9, 8, 4, 4, 4, 10};
        selectionSort(arr);
    }
}

插入排序

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
                swap(arr, j, j - 1);
            }
            System.out.println(Arrays.toString(arr));
        }
    }

    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {15, 4, 5, 2, 7, 12, 6, 1, 4, 3, 9, 8, 4, 4, 4, 10};
        insertionSort(arr);
    }
}

计数排序

public class CountingSort {                             //计数排序，如果数据是离散的？
    public static void countingSort(int[] arr) {
        if (arr.length < 1) {
            return;
        }
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        int[] count = new int[max + 1];             //创建计数数组
        for (int i = 0; i < arr.length; i++) {
            count[arr[i]]++;
        }
        System.out.println(Arrays.toString(count));
        for (int i = 1; i < count.length; i++) {    //将计数数组转成累加数组，为了稳定性
            count[i] += count[i - 1];
        }
        System.out.println(Arrays.toString(count));
        int[] temp = new int[arr.length];           //创建临时数组存放数据
        for (int i = arr.length - 1; i >= 0; i--) {
            temp[count[arr[i]] - 1] = arr[i];       //temp[count[arr[i]] - 1]不会数组越界，因为如果arr[i]=0时count[arr[i]]肯定不为0
            count[arr[i]]--;
        }
        for (int i = 0; i < arr.length; i++) {      //把临时数组赋值给原数组
            arr[i] = temp[i];
        }
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 8, 1, 4, 9, 0, 7, 16, 14};
        countingSort(arr);
        String s = Arrays.toString(arr);
        System.out.println(s);
    }
}

堆排序

public class HeapSort {                                        //堆排序 升序使用大顶堆
    //维护堆的性质
    public static void heapify(int[] arr, int n, int i) {      // n为数组长度，i为当前维护节点下标
        int largest = i;
        int lson = i * 2 + 1;
        int rson = i * 2 + 2;
        if (lson < n && arr[largest] < arr[lson]) {             //找到左右子节点中最大的那个
            largest = lson;
        }
        if (rson < n && arr[largest] < arr[rson]) {
            largest = rson;
        }
        if (largest != i) {                                     //交换让父节点最大
            swap(arr, largest, i);
            heapify(arr, n, largest);                           //递归调用维护大顶堆性质
        }
    }

    public static void heapsort(int[] arr, int n) {
        //建堆
        for (int i = n / 2 - 1; i >= 0; i--) {              //从最后一个节点开始向上，对每个父节点使用heapify
            heapify(arr, n, i);                             //n/2-1是找到最后一个节点的父节点
        }
        //排序
        for (int i = n - 1; i > 0; i--) {
            swap(arr, i, 0);                            //交换堆顶堆底元素，因为堆顶元素绝对是最大的
            heapify(arr, i, 0);                         //从堆顶开始维护大顶堆性质，使堆顶元素变为最大的
        }
    }

    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }


    public static void main(String[] args) {
        int[] arr = {2, 3, 8, 1, 4, 9, 10, 7, 16, 14};
        heapsort(arr, arr.length);
        String s = Arrays.toString(arr);
        System.out.println(s);
    }
}

归并排序

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {3, 2, 7, 11, 5, 8, 10, 1, 4};
        int[] tempArr = new int[arr.length];
        mergesort(arr, tempArr, 0, arr.length - 1);
        String s = Arrays.toString(arr);
        System.out.println(s);
    }

    public static void mergesort(int[] arr, int[] tempArr, int left, int right) {
        if (left < right) {
            int middle = (right - left) / 2 + left;
            mergesort(arr, tempArr, left, middle);
            mergesort(arr, tempArr, middle + 1, right);
            merge(arr, tempArr, left, middle, right);
        }
    }

    public static void merge(int[] arr, int[] tempArr, int left, int middle, int right) {
        int l_pos = left;            // 左半区第一个未排序元素
        int r_pos = middle + 1;        // 右半区第一个未排序元素
        int pos = left;              // 临时数组元素下标

        // 合并
        while (l_pos <= middle && r_pos <= right) {
            if (arr[l_pos] < arr[r_pos]) {
                tempArr[pos++] = arr[l_pos++];
            } else {
                tempArr[pos++] = arr[r_pos++];
            }
        }
        while (l_pos <= middle) {
            tempArr[pos++] = arr[l_pos++];
        }
        while (r_pos <= right) {
            tempArr[pos++] = arr[r_pos++];
        }
        while (left <= right) {
            arr[left] = tempArr[left];
            left++;
        }
        System.out.println("    排序中：" + Arrays.toString(arr));
    }
}

快速排序

public class QuickSort {
    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];                                  //将最后一个数作为pivot，比pivot大的放在右边，小的放在左边
        int i = low - 1;
        for (int j = low; j < high; j++) {                      //为了比较第一个数，i需要是low-1而非low
            if (arr[j] < pivot) {
                swap(arr, j, ++i);
            }
        }
        // 此时i+1指向的元素一定大于pivot
        swap(arr, high, i + 1);
        return i + 1;
    }

    public static void quicksort(int[] arr, int low, int high) {
        if (low < high) {
            int mid = partition(arr, low, high);
            quicksort(arr, low, mid - 1);
            quicksort(arr, mid + 1, high);
        }
    }

    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {1,4,3,9,8};
        quicksort(arr, 0, arr.length - 1);
        String s = Arrays.toString(arr);
        System.out.println(s);
    }
}

希尔排序

public class ShellSort {

    public static void shellSort(int[] arr) {
        System.out.println(arr.length);
        for (int inc = arr.length / 2; inc > 0; inc /= 2) {          //初始增量length/2
            System.out.println(inc);
            for (int i = inc; i < arr.length; i++) {                 //从这个增量序列的第二个数开始遍历
                //arr[i] < arr[i - inc]：如果在此增量序列前一个数大于后一个数，交换这两个数的位置
                //i >= inc是保证数组不越界
                //i-=inc是为了比较这个增量序列中的每一个数
                while (i >= inc && arr[i] < arr[i - inc]) {
                    swap(arr, i, i - inc);
                    i -= inc;
                }
            }
            System.out.println(Arrays.toString(arr));
        }
    }

    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {15, 4, 5, 2, 7, 12, 6, 1, 4, 3, 9, 8, 4, 4, 4, 10};
        shellSort(arr);
    }
}

二分查找

public class BinarySearch {
    public static int binarySearch(int[] arr, int key) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (key > arr[mid]) {
                left = mid + 1;
            } else if (key < arr[mid]) {
                right = mid - 1;
            } else return mid;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 4, 5, 8, 9, 11, 12, 13, 14, 17, 19, 20, 21, 23};
        int i = binarySearch(arr, 1);
        System.out.println(i + 1);
    }
}