排序算法总结

相关资料

排序算法总结 - 图1

对于冒泡、选择、插入等采用比较和交换元素的排序方法，由于经常执行交换操作，通常将交换动作写为swap方法，需要交换时调用。最常见swap写法是利用一个临时数tmp来交换arr[i]，arr[j]。也可以通过arr[i]和和arr[j]的加减运算避免临时数tmp的开销，但由于涉及到加减法可能导致数字「提前溢出」。第三种方法利用位运算中的异或运算，能够避免tmp的开销且不会导致数字溢出。需要特别注意的是，「方法二」和「方法三」要避免 i = j ，若 i = j，执行swap后将导致该数字变为0。实际上自我交换总是不必要的，因此应当保证swap被调用时 i != j，这样就无需 if 语句了。

// 方法一: 利用临时数tmp
private void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}
// 方法二: 利用加减运算
private void swapCal(int[] arr, int i, int j) {
    if(i == j) return; // 若无法保证swapCal被调用时满足 i != j，则需有此句，否则i == j时此数将变为0
    arr[i] = arr[i] + arr[j]; // a = a + b
    arr[j] = arr[i] - arr[j]; // b = a - b
    arr[i] = arr[i] - arr[j]; // a = a - b
}
// 方法三: 利用异或运算
private void swapXOR(int[] arr, int i, int j) {
    if(i == j) return; // 若无法保证swapXOR被调用时满足 i != j，则需有此句，否则i == j时此数将变为0
    arr[i] = arr[i] ^ arr[j]; // a = a ^ b，也可写成 arr[i] ^= arr[j];
    arr[j] = arr[i] ^ arr[j]; // b = (a ^ b) ^ b = a ^ (b ^ b) = a ^ 0 = a， 也可写成 arr[j] ^= arr[i];
    arr[i] = arr[i] ^ arr[j]; // a = (a ^ b) ^ a = (a ^ a) ^ b = 0 ^ b = b， 也可写成 arr[i] ^= arr[j];
}
//异或 xor
a^=b;
b^=a;
a^=b;
既不会额外增加内存开销 也不会导致溢出

等差数列比如 1 2 3 4 5 6 或者 1 3 5 7 9
等差数列是常见数列的一种，可以用AP表示，如果一个数列从第二项起，每一项与它的前一项的差等于同一个常数，这个数列就叫做等差数列，而这个常数叫做等差数列的公差，公差常用字母d表示 [1] 。例如：1,3,5,7,9……（2n-1)。等差数列{an}的通项公式为：an=a1+(n-1)d。前n项和公式为：Sn=n*a1+n(n-1)d/2或Sn=n(a1+an)/2
冒泡排序比较n-1 轮第一轮比较n-1次最后一次比较1次共比较 n(n-1)/2 时间复杂度 o(n^2) 空间复杂度 o(1)

稳定性：稳定。
排序稳定性指的是相等元素在原输入数组中的相对位置，在排序后不变，否则排序不稳定。稳定性对于纯数字数组来说意义不大，但对于包含多个属性的类数组来说，用于比较的属性之外其他属性不同时，保持排序的稳定性就很重要了。
冒泡排序始终只交换相邻元素，比较对象大小相等时不交换，相对位置不变，故稳定。

————————————————————————————————
对于要排序的数组，设置一个minIdx记录最小数字下标。先假设第1个数字最小，此时minIdx = 0，将arr[minIdx]与后续数字逐一比较，当遇到更小的数字时，使minIdx等于该数字下标，第1轮比较将找出此时数组中最小的数字。找到后将minIdx下标的数字与第1个数字交换，此时称一个数字已被排序。然后开始第2轮比较，令minIdx = 1，重复上述过程。每一轮的比较将使得当前未排序数字中的最小者被排序，未排序数字总数减1。第arr.length - 1轮结束后排序完成。

如下动图展示了{4,6,2,1,7,9,5,8,3}的选择排序过程（单元选择）。

微优化：在交换前判断minIdx是否有变化，若无变化则无需交换。当数组大致有序时，能够减少无效交换带来的开销。

稳定性：不稳定。

存在跨越交换。找到本轮次最小值之后，将其与本轮起始数字交换，此时若中间有与起始元素同值的元素，将打破稳定性。

例:　7 7 2 。第一轮交换第一个7和2，则两个7位置关系改变。

相关资料