/------------------冒泡排序
外层 len - 1 里层 j < len - i - 1
大数下沉
1)比较相邻的元素。如果第一个比第二个大,就交换他们两个。
2)对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。
在这一点,最后的元素应该会是最大的数。
3)针对所有的元素重复以上的步骤,除了最后一个。
4)持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
/* 78 10 15 65 3 //len = 5 len - 1 = 4//外层循环了len-1 次
----------------------
10 15 65 3 78 //循环了4ci // 内层循环了len - i -1次
--------------------
10 15 3 65 78 //循环了3次
--------------------
10 3 15 65 78 //循环了2次
---------------------
3 10 15 65 78 //循环了1次
*/
for (int i=0; i<len-1; i++)
//每趟排序都会确定一个数,所以需要再循环len-i次,但因为每次都是 //相邻的两个数进行比较,为了a[j+1]不越界,让j循环到len-i-1时停止。
for (int j=0; j<len-i-1; j++) {
//若arr[j]>arr[j+1] 若前一位比后一位元素大,则交换顺序
if (arr[j]>arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
//------------------选择排序思想
外层 len-1 里层 j=i+1 j<len
int a[10]={23,12,4,67,20,100,21,45,3,28};
假设a[0]为最小,分别与a[1] a[2] ... 比较, 在比较过程中,如果有元素的值比a[0]小,交换值
第一种方法
//每一趟都是拿着一个元素与后面其他元素进行比较,找出最小值
void selectSort1(int array[],int len){
// 1、确定需排序趟数
for (int i = 0 ; i < len - 1; i++) { // 2、每一趟怎么处理
for (int j = i + 1; j < len; j++) {
if (array[i] > array[j]) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
}
第二种方法
void selectSort2(int arr[],int len){
int temp;
int min;
for (int i=0; i<len - 1; i++) {
//每次假设第arr[i]是最小值 min = i;
min = i;
for (int j=i+1; j<len; j++) {
//找到最小的那个元素的下标
if (arr[j]<arr[min]) min=j;
}
//如果没有找到比arr[i]小的,就不用交换 if(i!= min){
//将第i个元素和最小的元素交换 temp=arr[i];
temp = arr[i];
arr[i]=arr[min];
arr[min] = temp; }
}
//打印数组
for (int i=0; i<len; i++) {
printf("%d\t",arr[i]); }
}
//----- 冒泡:
外层for (int i=0; i<len-1; i++)
内层for (int j=0; j<len-i-1; j++)
//----- 选择排序:
外层for (int i=0; i<len - 1; i++)
内层for (int j=i+1; j<len; j++)
//------------------折半查找思想
思路: 先划分空间,再在其空间查找,取中间点,中间点往左,元素的值一定比中间值小,右边的值一定比中间值大.
判断 关键点 if (key>arr[mid]) {low = mid+1;} //右半区查找
if (key<arr[mid]){high = mid - 1;} //左半区查找
找 12
low high
0 1 2 3 4 5 6 7 8 9
// 3 4 12 20 21 23 28 45 67 100
--------------------------------------------
1 low mid high
2 low mid high
3 low high
mid = (low + high) / 2 = 4;
a[4] = 21 > 12 --> high = mid - 1 ---> 4 - 1 = 3
mid = (low + high)/2 = 1;
a[1] = 4 < 12 --> low = mid + 1 --> 1+1 = 2
mid = (2+3)/2 --> 2
a[2] = 12 == 12
//折半查找
int searchItem(int arr[],int len,int key){
//先要定义变量
int low=0,high=len-1,mid;
//循环
while (low<=high) {
// 计算 mid的位置
mid = (low+high)/2;
printf("mid = %d",mid);
// 判断 key a[mid],右半区查找
if (key>arr[mid]) {
// key > a[mid] low = mid +1;
low = mid+1;
}else if (key<arr[mid]){
// key < a[mid] high = mid -1;
high = mid - 1;
}else{
// key == a[mid] //return mid;
return mid;
}
}
// 下面是查找不到的情况
return -1;
}
//折半插入 不建议看
int insertItemLoc(int arr[],int len,int key){
//先要定义变量
int low=0,high=len-1,mid;
//循环
while (low<=high) {
// 计算 mid的位置
mid = (low+high)/2;
// 判断 key a[mid],右半区查找
if (key>arr[mid]) {
// key > a[mid] low = mid +1;
low = mid+1;
}else if (key<arr[mid]){
// key < a[mid] high = mid -1;
high = mid - 1;
}else{
// key == a[mid] //return mid;
return mid + 1;
}
}
// 下面是查找不到的情况
return low;
}
|
|