交换排序是一类借助交换排序的算法，其主要思想是：在待排序序列中选两个记录，将它们的关键码进行比较，如果反序则交换它们的位置。
一、起泡排序
起泡排序是交换排序中最简单的算法，基本思想：两两比较相邻记录的关键码，如果反序则交换，直到没有反序的记录。代码如下
function bubbleSort(arr){ var length=arr.length; var exchange=length-1,bound,temp; while(exchange!=0){ bound=exchange; exchange=0; for(var j=0;j<length;j++){ if(arr[j]>arr[j+1]){ temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; exchange=j; } } } return arr; } bubbleSort([4,3,5,6]);
效率：
时间复杂度：最好：O(n)，最坏：O(n^2)，平均：O(n^2)。
空间复杂度：O(1)。
稳定性：稳定
备注：冒泡排序，思想和起泡排序一样，但是比较的次数>=起泡排序。代码如下：
/*冒泡排序*/ function sort(arr) { for (i = 1; i < arr.length; i++) { for (j = 0; j < i; j++) { if (arr[j] > arr[i]) { maxTemp = arr[j]; arr[j] = arr[i]; arr[i] = maxTemp; } } } return arr; } console.log(sort([5, 100, 6, 3, -12]));
一、快速排序
起泡排序的比较和移动是在相邻的位置进行的，记录每次只能后移一个位置，因此总的比较和移动次数比较多，在快速排序中，记录的比较和移动是从两端向中间进行，关键码较大的记录一次就能从前面移动到后面，关键码较小的记录一次就能从后面移到前面，记录移动的距离较远，从而减少了总的比较次数和移动次数，快速排序又称为分区交换排序，基本思想：首先选一个轴值（即比较的基准），将待排序序列分成两部分，左侧记录的关键码均小于或等于轴值，右侧记录的关键码均大于或等于轴值，然后分别对这两个部分重复上述过程知道整个序列有序，这是一个递归的过程。代码如下：
/*快速排序*/ function Sort(arr) { if (arr.length <= 1) { return arr; } //取中间数值 var standardNum = arr.splice(Math.floor(arr.length / 2), 1); var leftArr = []; var rightArr = []; for (var i = 0; i < arr.length; i++) { if (arr[i] <= standardNum[0]) { leftArr.push(arr[i]); } else { rightArr.push(arr[i]); } } return Sort(leftArr).concat(standardNum, Sort(rightArr)); } Sort([5, 100, 6, 3, -12]); //[-12, 3, 5, 6, 100]
改进版：
function quickSort(arr) {
let swap = (arr, i, j) => {
let tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
let partition = (arr, first, end) => {
var i = first;
var j = end;
while(i < j) {
while(i < j && arr[i] <= arr[j]) {
j--;
}
if(i < j) {
swap(arr, i, j);
}
while(i < j && arr[i] <= arr[j]) {
i++;
}
if(i < j) {
swap(arr, i, j)
j--;
}
}
return i;
}
let sort = (arr, first, end) => {
if(first < end) {
mid = partition(arr, first, end);
sort(arr, first, mid - 1);
sort(arr, mid + 1, end);
}
}
sort(arr, 0, arr.length - 1);
return arr;
}
var arr = [23, 13, 49, 6, 31, 19, 28]
quickSort(arr);
效率：
时间复杂度：最好：O(nlog2n)，最坏：O(n^2)，平均：O(nlog2n)。
空间复杂度：O(log2n)~O(n)。
稳定性：不稳定
快速排序适用于待排序记录个数很大且原始记录随机排列的情况，平均性能是迄今为止所有排序算法中最好的一种。
三、利用快排的思想找一个无序数组的中位数
如果数组长度是奇数，中位数是排序后的第(n+1)/2个元素；若是偶数，中位数是排序后第n/2个元素。
换个思路：从无序数组中查找第k大的元素。
利用快速排序的partition函数，任意挑一个元素，以该元素key，划分数组为两部分，key左边元素小于等于key，右边元素大于等于key。
在第一次partition后，如果左侧元素个数 < k - 1，则在右侧子序列中递归查找；
如果左侧元素个数 = k-1，则第k大元素即在分点处；
如果左侧元素个数 > k - 1,则递归地在左侧序列中继续查找。代码如下：
function findNum(arr) { let swap = (arr, i, j) => { let tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } let partition = (arr, first, end) => { var i = first; var j = end; while(i < j) { while(i < j && arr[i] <= arr[j]) { j--; } if(i < j) { swap(arr, i, j); } while(i < j && arr[i] <= arr[j]) { i++; } if(i < j) { swap(arr, i, j) j--; } } return i; } // 第k大的数，如果数组长度奇数，则k = (1+n)/2, 否则 k= n/2 function findMediate(arr, k, low, high) { if(k > high - low + 1) { return -1; } let pos = partition(arr, low, high); if(pos - low < k - 1) { return findMediate(arr, k - pos - 1, pos + 1, high); } else if(pos - low == k - 1) { return arr[pos]; } else { return findMediate(arr, k, low, pos - 1); } } function main(arr) { let res; if(arr.length%2 == 1) { res = findMediate(arr, (arr.length+1)/2, 0, arr.length-1); } else { res = findMediate(arr, arr.length/2, 0, arr.length-1); } return res } return main(arr); } var arr = [23, 13, 49, 6, 31, 19, 28, 30, 50] findNum(arr); // 28 var arr = [23, 13, 49, 6, 31, 19, 28] findNum(arr); // 23 var arr = [23, 13, 49, 6, 31, 19, 28, 30] findNum(arr); // 23