排序算法
冒泡排序
/*
* 开始用的是从n-1的元素进行比较，这是正规的冒泡排序算法
*/
void BubbleSort(int k[],int n)
{
int i,j,temp;
for (i = 0; i <n; i++) {
for (j =n-1; j>i; j--) {
if (k[j] < k[j-1]) {
temp =k[j-1];
k[j-1] = k[j];
k[j] = temp;
}
}
}
for (int i =0 ; i<n; i++) {
printf("%d ",k[i]);
}
printf("\n");
}
选择排序
void SelectSort(int k[],int n){
int i,j,temp;
for (i = 0; i<n; i++) {
int min = i;
for (j = i+1; j<n; j++) {
if (k[j] < k[min]) {
min = j;
}
}
//如果i发生了变化，才会进行位置交换
if (min != i) {
temp = k[i];
k[i] = k[min];
k[min] = temp;
}
}
for (int i =0 ; i<n; i++) {
printf("%d ",k[i]);
}
printf("\n");
}
冒泡排序和选择排序的核心思路：
- 冒泡排序是：相邻两个元素两两进行比较，小则交换位置。
- 选择排序是：进行一轮比较，把最小的那个数拿出来。直到本轮比较完成后，才进行换位置。这样的效率在一定程度上高于冒泡排序。
直接插入排序
void InserSort(int k[],int n){
int i,j,temp;
for (i = 1; i<n; i++) {
if (k[i] < k[i-1]) {
//先保存最小值
temp = k[i];
//k[j] >temp核心的判断条件
for (j = i-1; k[j] >temp; j--) {
//找位置向后推移,
k[j+1] = k[j];
}
printf("%d ",j);//打印结果为-1，所以k[j+1]其实就是k[0];
k[j+1] = temp;
}
}
}
直接插入排序算的核心：
举例：
int k[] = {3,5,2};
第一次比较后，还是 3，5，2
第二次比较的详细过程：
temp = 2；
执行
for (j = i-1; k[j] >temp; j--)
{
k[j+1] = k[j];
}
此时，j=1,k[1]=5>2;执行k[j+1] = k[j];
所以，k[2]=5,
现在的int k[]={3,5,5};
----------------------------------------------------------
继续 j--,此时，j=0,k[0]=3>2；执行k[j+1] = k[j];
所以，k[1]=3,
现在的int k[]={3,3,5};
----------------------------------------------------------
继续 j--，j=-1,跳出循环
此时，
现在的int k[]={3,3,5};
执行 k[j+1] = temp;//j=-1
现在的int k[]={2,3,5};
完成
