冒泡排序
从待排序列的一端两两比较相邻元素,若是前一个较大就交换(假设是从小到大排),按照这种方式,每一轮都可以将一个当前待排序列中最小的元素放置到有序序列中。
在数组中,就是每一轮将当前轮最小的元素放置到数组末尾,同时将末尾排除出下一轮比较。直到结束。
#include <iostream>
using namespace std;
void bubble_sort(int arr[], int len)
{
int i, j, temp;
for(i = 0; i < len; i++)
{
for(j = len - 1; j > i; j--)
{
if(arr[j] < arr[j-1])
{
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
}
}
int main()
{
int arr[] = {7, 1, 4, 8, 3, 2};
int len = sizeof(arr)/sizeof(int);
for(int i = 0; i < len; i++)
{
cout << arr[i] << endl;
}
cout << "-------" << endl;
bubble_sort(arr, len);
for(int i = 0; i < len; i++)
{
cout << arr[i] << endl;
}
return 0;
}
冒泡排序改进版
如果待排序列原本有序抑或是经过几次交换后有序,这时候再继续进行两两比较就没有意义了。所以增加一个flag标志,当一轮比较循环没有发生交换的情况,就说明序列已经有序,这时候就停止比较,结束程序。
void bubble_sort(int arr[], int len)
{
int i, j, temp;
bool flag;
for(i = 0; i < len; i++)
{
flag = false;
for(j = len - 1; j > i; j--)
{
if(arr[j] < arr[j-1])
{
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
flag = true;
}
}
if(flag == false)
return;
}
}
注意看增加的flag。
快速排序
基本思想基于分治。选定一个元素作为枢轴值,一次排序将序列分为两部分,一部分元素都比枢轴值大,一部分都比枢轴值小。然后递归进行这项操作,直到每部分内只有一个元素或为空。
#include <iostream>
using namespace std;
int partition(int arr[], int low, int high)
{
int pivot = arr[low]; //设置枢轴值。
while(low < high) //循环结束条件。
{
while(low<high && arr[high]>=pivot) //将比枢轴值pivot小的元素移到左端。
--high;
arr[low] = arr[high];
while(low<high && arr[low]<=pivot) //将比枢轴值pivot大的元素移到右端。
++low;
arr[high] = arr[low];
}
arr[low] = pivot; //枢轴值存放的最终位置。
return low; //返回枢轴值的存放位置。
}
void quick_sort(int arr[], int low, int high)
{
if(low < high) //递归结束条件。
{
int pivotpos = partition(arr, low, high); //子序列划分,pivotpos为划分的枢轴值。
quick_sort(arr, low, pivotpos-1); //对子序列进行排序。
quick_sort(arr, pivotpos+1, high);
}
}
int main()
{
int arr[] = {7, 1, 4, 8, 3, 2};
int len = sizeof(arr)/sizeof(int);
for(int i = 0; i < len; i++)
{
cout << arr[i] << endl;
}
cout << "-------" << endl;
quick_sort(arr, 0, len-1);
for(int i = 0; i < len; i++)
{
cout << arr[i] << endl;
}
return 0;
}