交换排序:冒泡排序,快速排序

交换排序指当元素位置相反时则把两个元素交换一下.多次重复这样的步骤则可排好所有的序.冒泡排序和快速排序都属于交换排序.

冒泡排序

一讲到冒泡两字你就会想到水里早泡泡,当然我们要做个假设,就是最轻的泡泡最先泡出来.

方法1:于是根据这样的思路,从右到左遍历一下数组,比较相邻的两元素,交换位置把小的放前面.这样一路下来,所有数组中最小的就跑前面去了.接下来把剩下的元素再遍历两两对比并交换,又会得到第二小的.一直这样重复.

方法2:我们可以把最小的元素冒出来放前面,那么根据反向思维,先遍历把最大的找出来放后面也达到同样的效果.

方法1:先交换出最小的元素

void BubbleSortLittle(int* arr , int len) //arr是指向数组的指针,len是数组长度

{

int tmp;

for(int i = 0; i < len - 1; i++)//从左至右遍历

{

for(int j = len - 1; j > i; j--) //从右至左遍历

{

if(arr[j] < arr[j - 1]) //后面的数小于前面的则交换

{

tmp = arr[j];

arr[j] = arr[j - 1];

arr[j - 1] = tmp;

}

}

}

}

方法2:先交换出最大的元素

void BubbleSortBig(int* arr, int len)

{

int tmp;

for(int i = len - 1; i > 0; i --) //从右至左遍历

{

for(int j = 0; j < i; j ++) //从左至右遍历

{

if(arr[j] > arr[j+1]) //前面的数大于后面的则交换

{

tmp = arr[j];

arr[j] = arr[j+1];

arr[j+1] = tmp;

}

}

}

}

测试代码:

int arr[] = { 1,3,2,4,5,7,6,8,9};

int len = sizeof(arr)/sizeof(int);

//BubbleSortLittle(arr , len);

BubbleSortBig(arr, len);

快速排序

我们知道假如一个已排好序的数组,假如是从小到大升序排列,则随便取其中一个数N,则N左边所有数都小于N,右边的都大于N.

那反向思维下,我们先随便取数组第一个数为基准X,然后将所有小于它的数交换到左边,大于它的数交换到右边.最后X可能就被交换到中间某个位置.以X为分界线,数组被分成两部分.接着再对两部分重复同样的操作.这里用到了递归的思想.

快速排序里面的元素交换又叫填坑,首先取出一个值做标准值X,则该值所在的位置i变成一个坑,从后面开始遍历碰到大于X的值(假如下标是j)就把该值交换到位置i,这样位置j就多出一个坑,从前面遍历,碰到大于tmp的值(假如位置是i)则把该值交换到位置j.这样i又多出一个坑. 这样不停的从后到前遍历,从前到后遍历,i与j值不断的变.最后i == j时停止.

void QuickSort(int* arr, int left , int right) //这里只需要数组第一和最后一个下标.

{

if(left < right)

{

int i = left;

int j = right;

int tmp = arr[left]; //就取左边第一个数为基准值.

while( i < j) //当i == j时退出循环

{

while( i < j && arr[j] >= tmp) //从后向前遍历,碰到小于tmp的值时停止,该值的索引肯定是j

j--;

if(i < j)

{

arr[i] = arr[j]; //把小于tmp的值arr[j]放到位置i

i++;

}

while(i < j && arr[i] < tmp) //从前向后遍历,碰到大于tmp的值停止,该值的索引肯定是i

i++;

if(i< j)

{

arr[j] = arr[i]; //把大于tmp的值arr[i]放到位置j

j --;

}

}

arr[i] = tmp; //当i = j时退出循环,基准传值被交换到位置i

QuickSort(arr, left , i - 1); //以基准值tmp为界,用同样的方式递归调用tmp左边的部分

QuickSort(arr, i + 1, right); //递归调用右边的部分

}

}

测试代码:

int arr[] = { 1,3,2,4,5,7,6,8,9};

int len = sizeof(arr)/sizeof(int);

QuickSort(arr, 0 , len - 1);