查找和排序
目录
排序
选择排序
选择排序通过每次选择未排序部分中的最小（或最大）元素，将其放置到已排序部分的末尾来排序整个数组。
时间复杂度：O(n^2)
c
#include <stdio.h>
int main()
{
int a[10] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0};
int i, j, t;
for (i = 0; i < 9; i++)
{
int min = i;
for (j = i + 1; j < 10; j++)
{
if (a[min] > a[j])
{
min = j;
}
}
}
for (i = 0; i < 10; i++)
{
printf("%d ", a[i]);
}
// 暂停
getchar();
return 0;
}冒泡排序
- 冒泡排序通过反复交换相邻的元素来逐步把较大的元素“冒泡”到数组的末尾，直到数组完全有序。
- 在每一轮遍历中，算法从数组的开始位置出发，依次比较相邻的两个元素。如果前一个元素大于后一个元素，则交换它们的位置。
- 每一轮遍历结束后，最大值会被移到数组的末尾，因此下一轮遍历时，可以忽略这个已经排序的部分。
c
#include <stdio.h>
int main()
{
int a[10] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0};
int i, j, t;
for (i = 0; i < 9; i++)
{
for (j = 0; j < 9 - i; j++)
{
if (a[j] > a[j + 1])
{
t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
}
}
}
for (i = 0; i < 10; i++)
{
printf("%d ", a[i]);
}
// 暂停
getchar();
return 0;
}插入排序
插入排序通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
c
#include <stdio.h>
int main()
{
int a[10] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0};
int i, j, t;
for (i = 1; i < 10; i++)
{
t = a[i];
for (j = i - 1; j >= 0 && a[j] > t; j--)
{
a[j + 1] = a[j];
}
a[j + 1] = t;
}
for (i = 0; i < 10; i++)
{
printf("%d ", a[i]);
}
// 暂停
getchar();
return 0;
}折半插入排序
折半插入排序是对插入排序的一种改进，它通过减少比较次数来提高排序效率。
c
#include <stdio.h>
int main()
{
int a[10] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0};
int i, j, t;
for (i = 1; i < 10; i++)
{
int low = 0, high = i - 1;
t = a[i];
while (low <= high)
{
int mid = (low + high) / 2;
if (a[mid] > t)
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
for (j = i - 1; j >= low; j--)
{
a[j + 1] = a[j];
}
a[low] = t;
}
for (i = 0; i < 10; i++)
{
printf("%d ", a[i]);
}
// 暂停
getchar();
return 0;
}快速排序
快速排序是对冒泡排序的一种改进，它通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
c
#include <stdio.h>
void quickSort(int a[], int low, int high)
{
if (low >= high)
return;
int i = low, j = high, t = a[low];
while (i < j)
{
while (i < j && a[j] >= t)
j--;
while (i < j && a[i] <= t)
i++;
if (i < j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
a[low] = a[i];
a[i] = t;
quickSort(a, low, i - 1);
quickSort(a, i + 1, high);
}
int main()
{
int a[10] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0};
quickSort(a, 0, 9);
for (int i = 0; i < 10; i++)
{
printf("%d ", a[i]);
}
// 暂停
getchar();
return 0;
}查找
折半查找
折半查找是对于有序数组的一种查找方法，它通过将待查找的元素与数组的中间元素进行比较，如果待查找元素小于中间元素，则在数组的前半部分继续查找，否则在数组的后半部分继续查找。
- 需要数组有序
- 中间 mid 使用
low + (high - low) / 2防止溢出（mid = (low + high) / 2有可能溢出）
c
#include <stdio.h>
int binarySearch(int a[], int n, int key)
{
int low = 0, high = n - 1;
while (low <= high)
{
int mid = low + (high - low) / 2;
if (a[mid] == key)
return mid;
else if (a[mid] > key)
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
int main()
{
int a[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
printf("%d\n", binarySearch(a, 10, 5));
// 暂停
getchar();
return 0;
}