十大排序算法之Java实现

选择排序

首先找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）。其次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。这种方法我们称之为选择排序。

public class SelectSort {
    public static int[] selectSort(int[] a) {
        int n = a.length;
        for(int i = 0; i < n; i++) {g
            int min = i;
            for(int j = i+1; j < n; j++) {
                if(a[min] > a[j]) min = j;
            }

             // 交换
             int temp = a[i];
             a[i] = a[min];
             a[min] = temp;
        }
        return a;
    }
}

1、 时间复杂度：O(n²)

2、空间复杂度：O(1)

3、非稳定排序

4、原地排序

插入排序

插入排序的一个简单理解就是我们平时在打牌时，将每一张牌插入到其他已经有序的牌中的适当位置。当我们给无序的数组做排序时，为了插入元素，我们需要先腾出空间，将其余所有元素在插入之前都向右移动一位，这种算法我们称之为插入排序。

public class InsertSort {
    public static int[] insertSort(int[] arr) {
        if(arr == null || arr.length < 2)
            return arr;

        int n = arr.length;
        for(int i = 1; i < n; i++) {
            int temp = arr[i];
            int k = i - 1;

            while(k >= 0 && arr[k] > temp)
                k--;
            // 腾出位置插进去，要插的位置是k+1
            for(int j = i; j > k; j--)
                arr[j] = arr[j-1];
            
            // 插进去
            arr[k+1] = temp;
        }
        return arr;
    }
}

1、 时间复杂度：O(n²)

2、空间复杂度：O(1)

3、稳定排序

4、原地排序

冒泡排序

把第一个元素与第二个元素相比较，如果第一个比第二个大，则交换他们的位置。接着继续比较第二个与第三个元素，如果第二个比第三个大，则交换他们的位置...

非优化版本

public class BubbleSort {
    public static int[] bubbleSort(int[] arr) {
        if(arr == null || arr.length < 2) {
            return arr;
        }
        int n = arr.length;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                int t = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = t;
            }
        }
        return arr;
    }
}

 1、 时间复杂度：O(n²)

2、空间复杂度：O(1)

3、稳定排序

4、原地排序

优化版本

 假如从开始的第一对到结尾的最后一对，相邻的元素之间都没有发生交换的操作，这意味着右边的元素总是大于等于左边的元素，此时的数组已经是有序的了，我们无需再对剩余的元素重复比较下去了。基于这点我们可以对上述代码做如下优化。

public class BubbleSort {
    public static int[] bubbleSort(int[] arr) {
        if(arr == null || arr.length < 2) {
            return arr;
        }
        int n = arr.length;
        for(int i = 0; i < n; i++) {
            boolean flag = true;
            for(int j = 0; j < n; j++) {
                if(arr[j+1] < arr[j]) {
                    flag = false;
                    int t = arr[j+1];
                    arr[j+1] = t;
                }
            }
            // 遍历一遍下来看是否发生过位置交换
            if(false)
                break;
        }
        return arr;
    }
}

希尔排序

public class ShellSort {
    public static int[] shellSort(int arr[]) {
        if(arr == null || arr.length < 2) return arr;
        int n = arr.length;
        // 对每组间隔为h的分组进行排序，刚开始h = n / 2;
        for(int h = n/2; h > 0; h /= 2) {
            int i = h; i < h; i++) {
                // 将arr[i]插入到所在分组的正确位置上
                insert(arr, h, i);
            }
        }
        return arr;
    }
    
    /**
     * 将arr[i]插入到所在分组的正确位置上
     * arr[i]所在分组为 ... arr[i-2*h], arr[i-h], arr[i+h] ...
    */
    private static void insertI(int[] arr, int h, int i) {
        int temp = arr[i];
        int k;
        for(k = i-h; k > 0 && temp < arr[k]; k -= h) {
            arr[k+h] = arr[k];
        }
        arr[k+h] = temp;
    }
}

1、 时间复杂度：O(n²)

2、空间复杂度：O(1)

3、非稳定排序

4、原地排序

归并排序

递归式归并排序

public class MergeSort {
    public static int[] mergeSort(int[] arr, int left, int right) {
        // 如果left==right，表示数组只有一个元素，则不用递归排序
        if(left < right) {
            // 把大的数组分隔成两个数组
            int mid = (left + right) / 2;
            // 对左半部分进行排序
            arr = mergeSort(arr, left, mid);
            // 对右半部分进行排序
            arr = mergeSort(arr, mid+1, right);
            // 进行合并
            merge(arr, left, mid, right);
        }
        return arr;
    }

    // 合并函数，把两个有序的数组合并起来
    // arr[left..mif]表示一个数组，arr[mid+1..right]表示一个数组
    private static void merge(int[] arr, int left, int mid, int right) {
        // 先用一个临时数组把他们合并汇总起来
        int[] a = new int[right - left + 1];
        int i = left;
        int j = mid + 1;
        int k = 0;
        while(i <= mid && j <= right) {
            if(arr[i] < arr[j] {
                a[k++] = arr[i++];
            } else {
                a[k++] = arr[j++];
            }
        }
        while(i <= mid) a[k++] = arr[i++];
        while(j <= right) a[k++] = arr[j++];
        // 把临时数组复制到原数组
        for(i = 0; i < k; i++) {
            arr[left++] = a[i];
        }
    }
}

1、 时间复杂度：O(n²)

2、空间复杂度：O(n)

3、稳定排序

4、原地排序

非递归式归并排序

public class MergeSort {
    // 非递归式的归并排序
    public static int[] mergeSort(int[] arr) {
        // 子数组的大小分别是1, 2, 4, 8. ...
        // 刚开始合并的数组大小是1，接着是2，接着4，...
        for(int i = 1; i < n; i += i) {
            // 进行数组进行划分
            int left = 0;
            int mid = left + i - 1;
            int right = mid + i;

            // 进行合并，对数组大小为i的数组进行两两合并
            while(right < n) {
                // 合并函数和递归式的合并函数一样
                merge(arr, left, mid, right);
                left = right + 1;
               mid = left + i - 1;
               right = mid + 1;
            }

            // 还有一些被遗漏的数组的合并，因为不可能每个数组的大小都刚好为1
            if(left < n && mid < n) {
                merge(arr, left, mid, n - 1);
            }
        }
        return arr;
    }
}

快速排序

 我们先从数组中选择一个元素作为中轴元素，然后把数组中所有小于中轴元素的元素放在其左边，所有大于或等于中轴元素的元素放在其右边，显然，此时中轴元素所处的位置是有序。也就是说，我们无需再移动中轴元素的位置。

然后从中轴元素那里开始把大的数组切割成两个小的数组（两个数组都不包含中轴元素），接着我们通过递归的方式，让中轴元素左边的数组和右边的数组也重复同样的操作，知道数组的大小为1，此时每个元素都处于有序的位置。

public class QuickSort {
    public static int[] quickSort(int[] arr, int left, int right) {
        if(left < right) {
           // 获取中轴元素所处的位置
           int mid = partition(arr, left, right);

           // 进行分割
           arr = quickSort(arr, left, mid - 1);
           arr = quickSort(arr, mid + 1, right);
        }
        return arr;
    }

    private static int partition(int[] arr, int left, int right) {
        // 选取中轴元素
        int pivot = arr[left];
        int i = left + 1;
        int j = right;
        while(true) {
            // 向右找到第一个小于等于pivot的元素位置
            while(i <= j && arr[i] <= pivot) i++;
            // 向左找到第一个大于的等于pivot的元素位置
            while(i <= j && arr[j] >= pivot) j--;
            if(i >= j)
                break;
            // 交换两个元素的位置，使得左边的元素不大于pivot，右边的不小于pivot
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        arr[left] = arr[j];
        // 使中轴元素处于有序的位置
        arr[j] = pivot;
        return j;
    }
}

1、 时间复杂度：O(nlogn)

2、空间复杂度：O(logn)

3、非稳定排序

4、原地排序

堆排序

堆的特点就是堆顶的元素是一个最值，大顶堆的堆顶是最大值，小堆顶则是最小值。

堆排序就是把堆顶的元素与最后一个元素交换，交换之后就破坏了堆的特性。我们再把堆中剩余的元素再次构成一个大顶堆，然后再把堆顶元素与最后第二个元素交换....如此往复下去，等到剩余的元素只有一个的时候，此时的数组就是有序 的了。

public class Head {
    // 堆排序
    public static int[] headSort(int[] arr) {

        int n = arr.length;
        // 构建⼤大顶堆
        for (int i = (n - 2) / 2; i >= 0; i--) {
            downAdjust(arr, i, n - 1);
        }
        
        // 进⾏行行堆排序
        for (int i = n - 1; i >= 1; i--) {
            // 把堆顶元素与最后⼀一个元素交换
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            // 把打乱的堆进⾏行行调整，恢复堆的特性
            downAdjust(arr, 0, i - 1);
        }

        return arr;
    }

    // 下沉操作
    public static void downAdjust(int[] arr, int parent, int n) {
        // 临时保存要下沉的元素
        int temp = arr[parent];
        // 定位左孩⼦子节点的位置
        int child = 2 * parent + 1;
        // 开始下沉
        while (child <= n) {
            // 如果右孩⼦子节点⽐比左孩⼦子⼤大，则定位到右孩⼦子
            if(child + 1 <= n && arr[child] < arr[child + 1])
                child++;
            // 如果孩⼦子节点⼩小于或等于⽗父节点，则下沉结束
            if (arr[child] <= temp ) break;
            // ⽗父节点进⾏行行下沉
            arr[parent] = arr[child];
            parent = child;
            child = 2 * parent + 1;
        }
        arr[parent] = temp;
    }
}

 1、 时间复杂度：O(n²)

2、空间复杂度：O(1)

3、非稳定排序

4、原地排序

^基数排序

非优化版本

优化版本

^桶排序

public class BucketSort {
    public static int[] BucketSort(int[] arr) {
        if(arr == null || arr.length < 2) return arr;
        int n = arr.length;
        int max = arr[0];
        int min = arr[0];

        // 寻找数组的最⼤大值与最⼩小值
        for (int i = 1; i < n; i++) {
            if(min > arr[i])
                min = arr[i];
            if(max < arr[i])
                max = arr[i];
        }

        // 和优化版本的计数排序⼀一样，弄弄⼀一个⼤大⼩小为 min 的偏移值
        int d = max - min;
        // 创建 d / 5 + 1 个桶，第 i 桶存放 5*i ~ 5*i+5-1范围的数
        int bucketNum = d / 5 + 1;
        ArrayList<LinkedList<Integer>> bucketList = new ArrayList<>(bucketNum);

        // 初始化桶
        for (int i = 0; i < bucketNum; i++) {
            bucketList.add(new LinkedList<Integer>());
        }

        // 遍历原数组，将每个元素放⼊入桶中
        for (int i = 0; i < n; i++) {
            bucketList.get((arr[i]-min)/d).add(arr[i] - min);
        }

        // 对桶内的元素进⾏行行排序，我这⾥里里采⽤用系统⾃自带的排序⼯工具
        for (int i = 0; i < bucketNum; i++) {
            Collections.sort(bucketList.get(i));
        }

        // 把每个桶排序好的数据进⾏行行合并汇总放回原数组
        int k = 0;
        for (int i = 0; i < bucketNum; i++) {
            for (Integer t : bucketList.get(i)) {
                arr[k++] = t + min;
            }
        }
        return arr;
    }
}

性质：

1、时间复杂度：O(n+k)

2、空间复杂度：O(n+k)

3、稳定排序

4、⾮非原地排序

注：k 表示桶的个数