排序算法总结

/ 0评 / 0

冒泡排序(稳定)

public class BubbleSort {
    public static void sort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }

        int length = array.length;
        //外层:需要length-1次循环比较
        for (int i = 0; i < length - 1; i++) {
            //内层:每次循环需要两两比较的次数,每次比较后,都会将当前最大的数放到最后位置,所以每次比较次数递减一次
            for (int j = 0; j < length - 1 - i; j++) {
                if (array[j] > array[j+1]) {
                    //交换数组array的j和j+1位置的数据
                    swap(array, j, j+1);
                }
            }
        }
    }

    /**
     * 交换数组array的i和j位置的数据
     * @param array 数组
     * @param i 下标i
     * @param j 下标j
     */
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

插入排序(稳定)

public class InsertSort {
    public static void sort(int[] a) {
        if (a == null || a.length == 0) {
            return;
        }

        for (int i = 1; i < a.length; i++) {
            int j = i - 1;
            int temp = a[i]; // 先取出待插入数据保存,因为向后移位过程中会把覆盖掉待插入数
            while (j >= 0 && a[j] > temp) { // 如果待是比待插入数据大,就后移
                a[j+1] = a[j];
                j--;
            }
            a[j+1] = temp; // 找到比待插入数据小的位置,将待插入数据插入
				}
		
				// 另一种写法
				for (int i = 1; i < listSize; i++) {
				    for (int j = 0; j < i; j++) {
				        if (numList.get(i) < numList.get(j)) {
				            numList.add(j, numList.get(i));
				            numList.remove(i+1);
				        }
				    }
				}
    }
}

选择排序(不稳定)

public class SelectSort {
    public static void sort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;
            for (int j = i+1; j < arr.length; j ++) { //选出之后待排序中值最小的位置
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            if (min != i) {
								int temp = arr[i];
				        arr[i] = arr[min];
				        arr[min] = temp;
            }
        }
    }
}

希尔排序

//优化前
for (gap = n / 2; gap > 0; gap /= 2) //步长
		for (i = 0; i < gap; i++)        //直接插入排序
			for (j = i + gap; j < n; j += gap)
				//插入排序

//优化后
public class ShellSort {
    public static void sort(int[] arr) {
        int gap = arr.length / 2;
        for (;gap >= 1; gap = gap/2) { //不断缩小gap,直到1为止
            for(int i = gap; i < arr.length; i++) { //使用当前gap进行组内插入排序
                int j = i - gap;
                int temp = a[i];
                while(j >= 0 && a[j] > temp) {
                    a[j+gap] = a[j];
                    j -= gap;
                }
                a[j+gap] = temp;
            }
        }
    }
}

快速排序(不稳定)

public class QuickSort {
    /**
     * 快速排序(左右指针法)
     * @param arr 待排序数组
     * @param low 左边界
     * @param high 右边界
     */
    public static void sort2(int arr[], int low, int high) {
        if (arr == null || arr.length <= 0) {
            return;
        }
        if (low >= high) {
            return;
        }

        int left = low;
        int right = high;

        int key = arr[left];

        while (left < right) {
            while (left < right && arr[right] >= key) {
                right--;
            }
            while (left < right && arr[left] <= key) {
                left++;
            }
            if (left < right) {
                swap(arr, left, right);
            }
        }
        swap(arr, low, left);
        System.out.println("Sorting: " + Arrays.toString(arr));
        sort2(arr, low, left - 1);
        sort2(arr, left + 1, high);
    }

    public static void swap(int arr[], int low, int high) {
        int tmp = arr[low];
        arr[low] = arr[high];
        arr[high] = tmp;
    }
}

归并排序(稳定)

public class MergeSort {

    public static int[] sort(int [] a) {
        if (a.length <= 1) {
            return a;
        }
        int num = a.length >> 1;
        int[] left = Arrays.copyOfRange(a, 0, num);
        int[] right = Arrays.copyOfRange(a, num, a.length);
        return mergeTwoArray(sort(left), sort(right));
    }

    public static int[] mergeTwoArray(int[] a, int[] b) {
        int i = 0, j = 0, k = 0;
        int[] result = new int[a.length + b.length]; // 申请额外空间保存归并之后数据

        while (i < a.length && j < b.length) { //选取两个序列中的较小值放入新数组
            if (a[i] <= b[j]) {
                result[k++] = a[i++];
            } else {
                result[k++] = b[j++];
            }
        }

        while (i < a.length) { //序列a中多余的元素移入新数组
            result[k++] = a[i++];
        }
        while (j < b.length) {//序列b中多余的元素移入新数组
            result[k++] = b[j++];
        }
        return result;
    }

    public static void main(String[] args) {
        int[] b = {3, 1, 5, 4};
        System.out.println(Arrays.toString(sort(b)));
    }
}

堆排序

class HeapSort {
    private int[] nums = {12, 6, 4, 9, 1, 5, 14, 3};

    public void swap(int[] arr, int i, int j) {
        int tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }

    // 构造大根堆
    public int[] buildHeap() {
        // 变为下标从 1 开始的数组,方便计算
        int[] arr = new int[nums.length + 1];
        System.arraycopy(nums, 0, arr, 1, nums.length);

        // 下标从 1 开始的话,最后一个非叶子节点的下标是 i/2
        // 叶子节点是不需要堆化的
        for (int i = nums.length / 2; i > 0; i--) {
            heapify(arr, i, nums.length);
        }

        return arr;
    }

    // 将以下标 index 为根的二叉树进行堆化,len 表示数组总长度
    public void heapify(int[] arr, int index, int len) {
        while (true) {
            int left = index * 2;
            int right = left + 1;
            int maxIndex = index;

            // 下标 index(根), left(左子), right(右子), 看谁最大
            if (left <= len && arr[left] > arr[index]) {
                maxIndex = left;
            }
            if (right <= len && arr[right] > arr[maxIndex]) {
                maxIndex = right;
            }

            // 如果根节点最大,天然就是一个堆,直接 break
            if (maxIndex == index)
                break;

            // 否则根节点和大节点做交换,并继续堆化
            swap(arr, index, maxIndex);
            index = maxIndex;
        }
    }

    public int[] sort() {
        // 先构建堆结构
        int[] maxHeap = buildHeap();
        // 循环,把堆顶(最大的)换到最后面,再重新堆化
        int count = nums.length;
        while (count > 0) {
            swap(maxHeap, 1, count);
            count--;
            heapify(maxHeap, 1, count);
        }
        return maxHeap;
    }
}

发表评论

邮箱地址不会被公开。 必填项已用*标注