冒泡排序，选择排序，插入排序————o（n^2)

之所以将这三种排序放在一起，是因为从本质上来讲，三种排序都是相同的，时间复杂度都为o(n^2)，且都是稳定的（关键字相同的元素之间在排序后仍保持原有相对顺序）。 在这里对一个长度为n(下标从0 到n)的可排序序列进行排序。 在这里以对一个存放整型的数组为例（C语言）。 函数有： int cmp（element1 ，element2）； void swap（element1，element2）；

int cmp(int element1,int element2){//比较 return element1-element2 } void swap(size_t element1,size_t element2,int *numSequence){//交换 int temp; temp=numSequence[element1]; numSequence[element1]=numSequence[element2]; numSequence[element2]=temp; }

冒泡排序 ：

待排序中，从前往后，相邻元素比较，大的放在后面，完成一次遍历即可将当前排序序列最后位置的元素放在最后一位（最大元素）。两层循环。第一层循环遍历从n-1 到1的每个下标，记为i，每次循环找到下标为i的元素。第二个循环在前 i个元素中找到比较找到最大值，储存在第i个位置，故j应小于i。 这里是c语言的实现

void Bubble_Sort(int *numSequence,int n){ int i,j,flag=0; for(i=n-1;i>0;i--){//第一层循环，从n-1找到前i个元素中最大值放在下标为i的位置 flag=0; for(j=0;j<i;j++){ if(cmp(numSequence[j],numSequence[j+1])>0)swap(j,j+1,numSequence),flag=1;//比较并判断是否交换 } if(flag==0)break;//若未发生交换则说明不存在逆序对，序列已排好序 } }

引入flag判断每一次外层循环是否发生交换，若未发生交换则不存在逆序对，序列已排好序，退出循环。

插入排序：

遍历序列，向已排好的序列中不断插入元素。一个元素可看成排好序的。 C语言实现

void Insertion_Sort(int *numSequence,int n){ int i,j,tmp; for(i=1;i<n;i++){ //每次插入下表为i的数 tmp=numSequence[i];//tmp存储插入的数 for(j=i;j>=0;j--){//与前面的数比较，寻找插入位置 if(j>0&&cmp(numSequence[j-1],tmp)>0){ numSequence[j]=numSequence[j-1]; } else{ numSequence[j]=tmp; break; } } } }

选择排序：

遍历未排序序列，选择最大（小）元素放在当序列最后（前）位。 C语言实现

void Selection_Sort(int *numSequence,int n){ int i,j,maxlow; for(i=n-1;i>0;i--){ maxlow=0;//初始以下标为0作为最大元素的下标 for(j=0;j<i;j++){ if(cmp(numSequence[j+1],numSequence[maxlow])>0){ maxlow=j+1; } } swap(maxlow,i,numSequence); } }