作者:我是赵晓霆 | 来源:互联网 | 2023-10-10 16:23
简单排序如果有N个元素需要排序,那么首先从N个元素中找到最小的那个(称为第0小的)放在第0个位子上(和原来的第0个位子上的元素交换位置),然后再从剩下的N-1个元素中找到最小的放在
简单排序
如果有N个元素需要排序,那么首先从N个元素中找到最小的那个(称为第0 小的)放在第0个位子上(和原来的第0个位子上的元素交换位置),然后再从剩 下的N-1个元素中找到最小的放在第1个位子上,然后再从剩下的N-2个元素 中找到最小的放在第2个位子上……直到所有的元素都就位。
总共执行了1,2,3,4,5。。。。n次即s(s-1)/2,量级是s2
#include
#include
using namespace std;
void SelectSort(int a[],int size){for(int i=0;i}
int main(){int a[5]={85,34,23,29,100};SelectSort(a,5);
}
插入排序
- 将整个数组a分为有序的部分和无序的两个部分。前者在左边,后者在右边。
- 开始有序的部分只有a[0],其余都属于无序的部分
- 每次取出无序部分的第一个(最左边)元素,把它加入到有序部分。假设插 入到合适位置p, 则原p位置及其后面的有序部分元素,都向右移动一个位子。 有序的部分即增加了一个元素。
- 直到无序的部分没有元素
#include
#include
using namespace std;
void InsertSort(int a[],int size){for(int i=1;ia[i]){ //已排好序的最小元素大于无序元素int tmp=a[i];for(int k=i;k>j;k--){a[k]=a[k-1];}a[j]=tmp; break;//放到合适位置后就可以break出来,没有必要继续 } }} //输出 for(int i=0;i}
int main(){int a[5]={85,34,23,29,100};InsertSort(a,5);
}
冒泡排序
- 将整个数组a分为有序的部分和无序的两个部分。前者在右,后者在左边。
- 开始,整个数组都是无序的。有序的部分没有元素。
- 每次要使得无序部分最大的元素移动到有序部分第一个元素的左边。移动的 方法是:依次比较相邻的两个元素,如果前面的比后面的大,就交换他们的位 置。这样,大的元素就像水里气泡一样不断往上浮。移动结束有序部分增加了 一个元素。
- 直到无序的部分没有元素
#include
#include
using namespace std;
void InsertSort(int a[],int size){for(int i=size-1;i>0;i--){for(int j=0;ja[j+1]){int tmp=a[j];a[j]=a[j+1];a[j+1]=tmp;}}} //输出 for(int i=0;i}
int main(){int a[5]={85,34,23,29,100};InsertSort(a,5);
}