排序算法的稳定性大家应该都知道，通俗地讲就是能保证排序前两个相等的数据其在序列中的先后位置顺序与排序后它们两个先后位置顺序相同。即：如，如果A i == A j，Ai 原来在 Aj 位置前，排序后 Ai 仍然是在 Aj 位置前。
基本排序算法：
冒泡排序：两层for循环，外层循环次数=数组长度，使每个元素都参与比较，内层循环比较相邻的两个数，交换两个数，内层走完一轮完成一个元素的排序位置，因为每完成一次循环都回排序好一个元素，因此内层完成一次排序，下次排序即可减少一轮排序，又因为其他数都拍好了最后一位不用再排一次，内层循环可以-1
时间复杂度：最好O(n),最坏O(n2),平均O(n2) 空间复杂度：O(1) 稳定性：稳定 是否是比较算法：是
//冒泡排序
public static int[] maoPaoSort(int[] array) {
if (array == null) {
throw new IllegalArgumentException("digtals==null");
}
if (array.length <= 1) {
return array;
}
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
return array;
}
简单选择排序：两层for循环，外层循环是数组长度，假定第一个元素数是最小值，内层循环从i+1位置开始找到最小的元素，然后交换值
时间复杂度：最好O(n2),最坏O(n2),平均O(n^2) 空间复杂度：O(1) 稳定性：不稳定 是否是比较算法：是
//简单选择排序
public static int[] jianDanXuanZeSort(int[] array) {
if (array == null) {
throw new IllegalArgumentException("array==null");
}
if (array.length <= 1) {
return array;
}
for (int i = 0; i < array.length; i++) {
int minIndex = i;
for (int j = i+1; j < array.length; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
int temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
return array;
}
插入排序：外层for循环次数数组长度-1，最后一个数不用再排序，里层while循环从i和i+1开始比较， 使用int preIndex = i;，按照升序，如果i+1的数比前一个数小，则前一个数往后移，preIndex --，while循环结束交换值。
时间复杂度：最好O(n),最坏O(n2),平均O(n2) 空间复杂度：O(1) 稳定性：稳定 是否是比较算法：是
//简单插入排序
public static int[] jianDanInsertSort(int[] array) {
if (array == null) {
throw new IllegalArgumentException("array==null");
}
if (array.length <= 1) {
return array;
}
int currentValue;
for (int i = 0; i < array.length - 1; i++) {
int preIndex = i;
currentValue = array[preIndex + 1];
while (preIndex >= 0 && currentValue < array[preIndex]) {
//按照升序，后面的小，就往后移一个位置，preIndex-- 依次与前一个值对比，比自己大的都往后移，因为自己的位置空出来了，直到没有比自己大的了，就跳出了循环
array[preIndex + 1] = array[preIndex];
preIndex--;
}
//跳出循环后preIndex已经在preIndex + 1的地方，因为跳出循环之前preIndex--，
array[preIndex + 1] = currentValue;
}
return array;
}
希尔排序：希尔排序原理和简单插入排序一样，主要是针对数据量大的数组， gap = gap / 2;分组先把数组排序为较为有序的数组，gap最终变成1，这么做是减少交换，否则元素只能一小步一小步的交换移动，gap = gap / 2;并不是最好的分组，
时间复杂度：最好O(n1.3),最坏O(n2),平均不确定 空间复杂度：O(1) 稳定性：不稳定 是否是比较算法：是
//希尔排序
public static int[] ShellSort(int[] array) {
if (array == null) {
throw new IllegalArgumentException("array==null");
}
if (array.length <= 1) {
return array;
}
int tempSize = 0;
int len = array.length;
int gap = len / 2;
int currentValue;
while (gap > 0) {
for (int i = gap; i < len; i = i + gap) {
int preIndex = i - gap;
currentValue = array[i];
while (preIndex >= 0 && currentValue < array[preIndex]) {
System.out.println("preIndex=" + preIndex + "-----------gap=" + gap);
array[preIndex + gap] = array[preIndex];
preIndex = preIndex - gap;
}
array[preIndex + gap] = currentValue;
}
gap = gap / 2;
}
return array;
}
归并排序 ：归并排序思想是分而治之，递归将数组分班，分到不能再分，分到只剩1个数，然后两个数比较合并成两个数的数组，然后两个数组的再和其他的数组比较合并，最终完成排序
时间复杂度：最好O(nlog n),最坏O(nlog n),平均O(nlog n) 空间复杂度：O(N) 稳定性：稳定 是否是比较算法：是
//归并排序
public static int[] mergeSort(int[] array) {
if (array == null) {
throw new IllegalArgumentException("array==null");
}
if ((array.length < 2)) {
return array;
}
int mid = array.length / 2;
int[] left = Arrays.copyOfRange(array, 0, mid);
int[] right = Arrays.copyOfRange(array, mid, array.length);
return merge(mergeSort(left), mergeSort(right));
}
private static int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
for (int index = 0, leftIndex = 0, rightIndex = 0; index < result.length; index++) {
if (leftIndex >= left.length) {
//左边数组已经全部按顺序放到result，剩余的只要把右边的按顺序放入result就行，不用担心右边的排序不对，因为左右两边各自的排序是正确的
result[index] = right[rightIndex++];
} else if (rightIndex >= right.length) {
//同上
result[index] = left[leftIndex++];
} else if (left[leftIndex] > right[rightIndex]) {
//按升序排列，小的放入result，下标增加
result[index] = right[rightIndex++];
} else {
//按升序排列，小的放入result，下标增加
result[index] = left[leftIndex++];
}
}
return result;
}
快速排序：原理，随机取数组中的某个元素作为比较基准数并和末尾元素交换，指示器从传入的start-1下标开始，当前数小于基准数指示器++，指示器++后小于于当前数的下标说明上一次遍历时指示器没有++，这次指示器++后指向的元素是大于基准数的，所以只是器的值要和当前遍历的值进行交换，一轮排序下来，小于等于基准数的都在左边，大于等于的都在右边，返回当前指示器，按照指示器分割数组递归调用自己，int[] array, int start, int end，array长度小于1或start>end或start<0或end大于array的长度结束循环。和归并排序有点相似。快速排序是比较常用的，因为比其他算法效率高（常数因子小）。还有双基准排序，比单基准快10%。（在递归调用时，当数组长度比较小时会采用如插入排序）
时间复杂度：最好O(nlog n),最坏O(n^2),平均O(nlog n) 空间复杂度：O(nlog n) 稳定性：不稳定 是否是比较算法：是
//快速排序
private static int[] quickSort(int[] array, int start, int end) {
if (array.length < 1 || start < 0 || end > array.length || start > end) {
return null;
}
int zoneIndex = partition(array, start, end);
if (zoneIndex > start) {
quickSort(array, start, zoneIndex - 1);
}
if (zoneIndex < end) {
quickSort(array, zoneIndex + 1, end);
}
return array;
}
private static int partition(int[] array, int start, int end) {
int pivot = (int) (start + Math.random() * (end - start + 1));//随机基准数的下标
int zoneIndex = start - 1;
swap(array, pivot, array[end]);
for (int i = start; i <= end; i++) {
if (array[i] <= array[end]) {
//按升序，如果当前数小于等于基准数，指示器右移
zoneIndex++;
if (zoneIndex < i) {
//右移指示器后，指示器又小于当前遍历数的下标，说明指示器对应的数值是大于基准数的，需要与当前遍历数交换
swap(array, zoneIndex, i);
}
}
}
return zoneIndex;
}
private static void swap(int[] array, int i, int j) {
int tamp = array[i];
array[i] = array[j];
array[j] = tamp;
}
堆排序：原理,构建完全二叉堆,升序就构建最大堆，降序就最小堆，最堆构建完成后，堆顶与堆尾交换，len--,排出一个有序元素，堆顶与堆尾交换后，最堆不成立，重新构建，如此循环，len==0完成排序。（缺点是需要反复的构建最堆，时间和空间复杂度总的比快速排序少，却不比快速排序效率高）
时间复杂度：最好O(nlog n),最坏O(nlog n) ,平均O(nlog n) 空间复杂度：O(nlog n) 稳定性：不稳定 是否是比较算法：是
//堆排序
private static int[] heapSort(int[] array) {
len = array.length;
if ((len < 1)) {
return array;
}
//升序排序，构建最大堆
buildMaxHeap(array);
//最大堆构建完成，堆顶元素和末尾元素交换，len-- 最大元素就被排序出来，重复此操作，得出排序
while (len > 0) {
swap(array, 0, len - 1);
len--;
adjustHeap(array, 0);
}
return array;
}
private static void buildMaxHeap(int[] array) {
//从最后一个非叶节点向前遍历
for (int i = (len / 2 - 1); i >= 0; i--) {
adjustHeap(array, i);
}
}
private static void adjustHeap(int[] array, int i) {
//以当前节点的值为最大值
int maxIndex = i;
//左节点
int leftIndex = 2 * i + 1;
//右节点
int rightIndex = 2 * (i + 1);
if ((leftIndex < len && array[leftIndex] > array[maxIndex])) {
//左节点存在并且左节点大于当前节点，更新最大值节点下标
maxIndex = leftIndex;
}
if ((rightIndex < len && array[rightIndex] > array[maxIndex])) {
//右节点
maxIndex = rightIndex;
}
if (maxIndex != i) {
//最大值节点不是非叶节点，交换值
swap(array, i, maxIndex);
//交换值后有可能不是一个最大完全二叉堆，递归调用自己,如从下往上，父节点被替换后，不满足最大堆，父节点的左右节点再来一次调整，完了之后子节点被调整后，其与其子节点又不符合最大堆，一直递归到没有子节点，结束后符合最大堆
adjustHeap(array, maxIndex);
}
}
private static void swap(int[] array, int i, int j) {
int tamp = array[i];
array[i] = array[j];
array[j] = tamp;
}
网友评论