概述
冒泡排序：从前（后）第一个数起与其后的第二个进行比较交换，以此往后，到第二个数与其后的第二个进行比较交换。最后一个数变为极大（小）值，以此从最后排序，形成冒泡。
#include <iostream>
using namespace std;
void show(int array[], int len)
{
int i = 0;
for(i=0; i<len; i++)
{
cout<<array[i]<<" ";
}
cout<<endl;
}
void swap(int array[], int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
void BubbleSort(int array[], int length)
{
int i = 0;
int j = 0;
for(i = 0; i < length; i++)
{
for(j = length-1; j > i; j--)
{
if( array[j] < array[j-1] )
{
swap(array, j, j-1);
}
show(array, length);
}
}
}
int main()
{
int array[] ={8,3,6,1};
int length = sizeof(array) / sizeof(*array);
cout<<"排序前"<<endl;
show(array, length);
cout<<endl;
BubbleSort(array, length);
cout<<endl;
cout<<"排序后"<<endl;
show(array, length);
return 0;
}
对冒泡排序的进一步的加强，加一个标志位，当某一趟冒泡排序没有元素交换时，则冒泡结束，元素已经有序，可以有效的减少冒泡次数。
#include <iostream>
using namespace std;
void show(int array[], int len)
{
int i = 0;
for(i=0; i<len; i++)
{
cout<<array[i]<<" ";
}
cout<<endl;
}
void swap(int array[], int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
void BubbleSort(int array[], int length)
{
int i = 0;
int j = 0;
bool if_finish = true;
for(i=0; (i<length) && if_finish; i++)
{
if_finish = false;
for(j=length-1; j>i; j--)
{
if( array[j] < array[j-1] )
{
swap(array, j, j-1);
if_finish = 1;
}
}
}
}
int main()
{
int array[] ={8,3,6,1};
int length = sizeof(array) / sizeof(*array);
show(array, length);
BubbleSort(array, length);
show(array, length);
return 0;
}
选择排序法：从第一个数起，选其后的最小的数与之交换，以此往后。
#include <iostream>
using namespace std;
void show(int array[], int len)
{
int i = 0;
for(i=0; i<len; i++)
{
cout<<array[i]<<" ";
}
cout<<endl;
}
void swap(int array[], int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
void SelectionSort(int array[], int length)
{
int i = 0;
int j = 0;
int sign = -1;
for(i=0; i<length; i++)
{
sign = i;
for(j = i+1; j<length; j++)
{
if( array[j] < array[sign] )
{
sign = j;
}
}
if(i != sign)
{
show(array, length);
swap(array, i, sign);
show(array, length);
cout<<endl;
}
}
}
int main()
{
int array[] ={4, 1, 3, 2};
int length = sizeof(array) / sizeof(*array);
cout<<"排序前"<<endl;
show(array, length);
cout<<endl;
SelectionSort(array, length);
cout<<endl;
cout<<"排序后"<<endl;
show(array, length);
return 0;
}
插入排序：从第一个数X起，与其之后遇到的第一个比其大（小）的数Y，并将Y前面个个数都后移一位，并将Y移至X，之后到第二个数，以此往后。。。。
#include <iostream>
using namespace std;
void show(int array[], int len)
{
int i = 0;
for(i=0; i<len; i++)
{
cout<<array[i]<<" ";
}
cout<<endl;
}
void swap(int array[], int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
void InertionSort(int array[], int length)
{
int i = 0;
int j = 0;
int sign = -1;
int temp = -1;
for(i=1; i<length; i++)
{
sign = i;
temp = array[sign];
for(j = i-1; (j>=0) && (array[j]>temp); j--)
{
array[j+1] = array[j];
sign = j;
}
array[sign] = temp;
show(array, length);
}
}
int main()
{
int array[] ={3, 1, 6, 5, 4, 2};
int length = sizeof(array) / sizeof(*array);
cout<<"排序前"<<endl;
show(array, length);
cout<<endl;
InertionSort(array, length);
cout<<endl;
cout<<"排序后"<<endl;
show(array, length);
return 0;
}
希尔排序：举例以效率比较高的3为例，n=length,n=n/3+1，第一个数与其后以3为倍数的个个数比较并排序，第二个数与其后以3为倍数的个个数比较并排序，以此为类...
#include <iostream>
using namespace std;
void show(int array[], int len)
{
int i = 0;
for(i=0; i<len; i++)
{
cout<<array[i]<<" ";
}
cout<<endl;
}
void swap(int array[], int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
void ShellSort(int array[], int length)
{
int i = 0;
int j = 0;
int k = -1;
int temp = -1;
int gap = length ;
while( gap > 1)
{
gap = gap / 3 + 1;
cout<<gap;
for(i=gap; i<length; i+=gap)
{
k = i;
temp = array[k];
for(j=i-gap; (j>=0) && (array[j]>temp); j-=gap)
{
array[j+gap] = array[j];
k = j;
}
array[k] = temp;
}
show(array, length);
}
}
int main()
{
int array[] ={7, 1, 6, 5, 4, 2};
int length = sizeof(array) / sizeof(*array);
cout<<"排序前"<<endl;
show(array, length);
cout<<endl;
ShellSort(array, length);
cout<<endl;
cout<<"排序后"<<endl;
show(array, length);
return 0;
}
快速排序：
#include <iostream>
using namespace std;
void show(int array[], int len)
{
int i = 0;
for(i=0; i<len; i++)
{
cout<<array[i]<<" ";
}
cout<<endl;
}
void swap(int array[], int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
int partition(int array[], int low, int high)
{
int pv = array[low];
while( low < high )
{
while( (low < high) && (array[high] >= pv) )
{
high--;
}
swap(array, low, high);
while( (low < high) && (array[low] <= pv) )
{
low++;
}
swap(array, low, high);
}
return low;
}
void QSort(int array[], int low, int high)
{
if( low < high )
{
int pivot = partition(array, low, high);
QSort(array, low, pivot-1);
QSort(array, pivot+1, high);
}
}
int main()
{
int array[] ={4, 1, 6, 5, 7, 2};
int length = sizeof(array) / sizeof(*array);
cout<<"排序前"<<endl;
show(array, length);
cout<<endl;
QSort(array,0,length-1);
cout<<endl;
cout<<"排序后"<<endl;
show(array, length);
return 0;
}
#include <iostream>
using namespace std;
void show(int array[], int len)
{
int i = 0;
for(i=0; i<len; i++)
{
cout<<array[i]<<" ";
}
cout<<endl;
}
void Merge(int src[], int des[], int low, int mid, int high)
{
int i = low;
int j = mid + 1;
int k = low;
while( (i <= mid) && (j <= high) )
{
if( src[i] < src[j] )
{
des[k++] = src[i++];
}
else
{
des[k++] = src[j++];
}
}
while( i <= mid )
{
des[k++] = src[i++];
}
while( j <= high )
{
des[k++] = src[j++];
}
}
void MSort(int src[], int des[], int low, int high, int max)
{
if( low == high )
{
des[low] = src[low];
}
else
{
int mid = (low + high) / 2;
int* space = (int*)malloc(sizeof(int) * max);
if( space != NULL )
{
MSort(src, space, low, mid, max);
MSort(src, space, mid+1, high, max);
Merge(space, des, low, mid, high);
}
free(space);
}
}
int main()
{
int array[] ={4, 1, 6, 5, 7, 2};
int length = sizeof(array) / sizeof(*array);
cout<<"排序前"<<endl;
show(array, length);
cout<<endl;
MSort(array, array, 0, length-1, length);
cout<<endl;
cout<<"排序后"<<endl;
show(array, length);
return 0;
}
最后
以上就是有魅力缘分为你收集整理的冒泡快速等算法总结的全部内容，希望文章能够帮你解决冒泡快速等算法总结所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复