排序算法
- 说实在的，这些算法都是应付面试用的，真正的iOS开发过程中，苹果都帮我们封装好了相对应的方法，简单省时省力，效率还高。当然了，研究算法可以提升自己的编程思想，以下案例都是从小到大排序
选择排序
- 取出第i个元素，依次和i后面的每一个元素对比，如果i+1元素比i元素小，那么交换元素值，然后接着拿交换后的元素值进行对比，直到对比到最后一个元素，其他元素以此类推
// 选择排序
int nums[8] = {99, 123, 22, 6, 2, 55, 67, 100};
// 计算长度
int length = sizeof(nums) / sizeof(nums[0]);
for (int i = 0; i < length; i++) {
for (int j = i + 1; j < length; j++) {
if(nums[i] > nums[j]){
// 交换元素值
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
}
冒泡排序
- 冒泡排序，就是用相邻的两个元素比较，每完全比较一次，最值就会出现在末尾
- 1和2，2和3，3和4.........以此类推
// 冒泡排序
int nums[8] = {99, 123, 22, 6, 2, 55, 67, 100};
int length = sizeof(nums) / sizeof(nums[0]);
for(int i = 0; i < length - 1; i++){
for (int j = 0; j < length - 1 - i; j++) {
if(nums[j] > nums[j + 1]){
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
}
折半查找
- 数组必须是有序的
- 必须已知min和max（知道范围）
- 动态计算mid的值，取出mid对应的值进行比较
- 如果mid对应的值大于需要查找的值，那么max = mid - 1
- 如果mid对应的值小于需要查找的值，那么min = mid + 1
// 折半查找第一种方式
int findKey1(int nums[], int length, int key)
{
int min, max, mid;
min = 0;
max = length - 1;
mid = (min + max) / 2;
while (key != nums[mid]) {
if (key > nums[mid]) {
// 判断如果要找的值，大于了取出的值，那么min要改变
min = mid + 1;
}else if(key < nums[mid]){
// 判断如果要找的值，小雨了取出的值，那么max要改变
max = mid - 1;
}
// 超出范围,数组中没有要查找的值
if(min > max){
return -1;
}
mid = (max + min) / 2;
}
return mid;
}
// 折半查找第二种方式
int findKey2(int nums[], int length, int key)
{
int min, max, mid;
min = 0;
max = length - 1;
// 只要还在范围内就需要查找
while (min <= max) {
// 计算中间值
mid = (max + min) / 2;
if(key > nums[mid]){
min = mid + 1;
}else if(key < nums[mid]){
max = mid - 1;
}else{
return mid;
}
}
return -1;
}
