六、双向冒泡排序
双向冒泡排序是冒泡排序的一种变体，冒泡排序每次比较都是从左向右，找出最大的放在最后。双向冒泡排序则是第一轮从左向右将最大的放最后，第二轮从右向左将最小的放最首，如此交替直到整个数列排序完成。文字描述双向冒泡排序步骤如下：
1.从左向右依次比较相邻两个元素，如果顺序不对，则进行交换，如此一轮下来，最大的元素在最后。
2.除去已经排序好的元素，从右向左依次比较相邻的两个元素，如果顺序不对，则进行交换，最小的元素在首部。
3.交替重复步骤1与步骤2直到排序完成。
双向冒泡排序示意图如下：
JavaScript实现的双向冒泡排序算法：
var array = [1,54,2,64,12,65,76,46,34,98];
//双向冒泡排序
var start = 0;
var end = array.length;
while(end-start>0){
//从左向右冒泡
for(var i=start;i<end-1;i++){
var temp = array[i];
if (array[i+1]<temp) {
array[i] = array[i+1];
array[i+1] = temp;
}
}
end--;
//从右向左冒泡
for(var j=end;j>start+1;j--){
var temp = array[j];
if (array[j-1]>temp) {
array[j] = array[j-1];
array[j-1] = temp;
}
}
start++;
}
console.log(array);//[ 1, 2, 12, 34, 46, 54, 64, 65, 76, 98 ]
C实现的双向冒泡排序算法：
#include <stdio.h>
//双向冒泡排序
void mySort(int array[],int size){
int start = 0;
int end = size;
//从左向右冒泡
for(int i=start;i<end-1;i++){
int temp = array[i];
if (array[i+1]<temp) {
array[i] = array[i+1];
array[i+1] = temp;
}
}
end--;
//从右向左冒泡
for(int j=end;j>start+1;j--){
int temp = array[j];
if (array[j-1]>temp) {
array[j] = array[j-1];
array[j-1] = temp;
}
}
start++;
}
int main(){
int a[] = {1, 2, 12, 34, 46, 54, 64, 65, 76, 98,33};
mySort(a,11);
for(int i = 0;i<11;i++){
printf("%d\n",a[i]);
}
return 0;
}
七、快速排序算法
快速排序算法和基本思路是通过一趟排序将数列分成两部分，其中一部分的所有数据都比另一部分小。之后在分别在两个子数列中进行递归，直到最终排序完成。快速排序算法的核心是递归，因此其效率十分高。用文字描述快速排序的步骤如下：
1.随机取一个元素作为基准，将小于此元素的数据都放在此元素的左侧，大于此元素的数据都放在此元素的右侧，将数列分隔成左右两个子数列。
2.分别对左右子数列进行步骤1的递归，直到数列长度为1或者0，表示排序完成。
JavaScript实现的快速排序算法：
var array = [1, 54, 2, 64, 12, 65, 76, 46, 34, 98, 34];
//快速排序
function sort(array, left, right) {
if (right - left >= 1) {
//取第一个元素作为基准
let base = array[left];
let i = left + 1;
let index = left;
while (i <= right) {
//大于等于的已经在右边 不需要修改 小于的要放在左边
if (array[i] < base) {
if (index + 1 == i) {
//交换
array[index] = array[i];
array[i] = base;
index++;
} else {
//先将base与其后一个元素交换
array[index] = array[index + 1];
array[index + 1] = base;
//交换
let temp = array[index];
array[index] = array[i];
array[i] = temp;
index++;
}
}
i++;
}
//递归排序
sort(array, left, index - 1);
sort(array, index + 1, right);
}
}
sort(array, 0, array.length - 1);
console.log(array); //[ 1, 2, 12, 34,34, 46, 54, 64, 65, 76, 98 ]
C语言实现的快速排序：
#include <stdio.h>
//快速排序
void mySort(int array[],int left,int right){
if(right-left>=1){
int base = array[left];
int i = left+1;
int index = left;
while(i<=right){
if(array[i]<base){
if(index+1==i){
array[index] = array[i];
array[i]=base;
index = i;
}else{
array[index]=array[index+1];
array[index+1] = base;
int temp = array[index];
array[index] = array[i];
array[i] = temp;
index++;
}
}
i++;
}
mySort(array, left, index-1);
mySort(array, index+1, right);
}
}
int main(){
int a[] = {1, 2, 12, 34, 46, 54, 64, 65, 76, 98,34};
mySort(a,0,10);
for(int i = 0;i<11;i++){
printf("%d\n",a[i]);
}
return 0;
}
