1.概述
算法是一组定义了一系列步骤或操作,以解决特定问题或执行特定任务的明确指令集合。
算法就是一种解决问题的步骤,就像是烹饪菜肴的食谱一样。想象你要做一道美味的披萨,你需要按照特定的顺序执行一系列步骤:准备面团、加入酱料、撒上配料,最后烤熟。这些步骤就是算法,它们告诉你该做什么以达到你想要的结果。
算法可以视为计算机科学中的计算过程或方法,用于解决各种问题,从简单的数学计算到复杂的数据处理和优化。
比如,如果你想要对一组数字进行排序,就需要一个排序算法。类似于烹饪食谱中的步骤,排序算法告诉计算机该如何将这些数字按照一定的顺序排列起来。
一个好的算法应当满足以下几个条件:
-
正确性: 算法必须能够在给定输入的情况下产生正确的输出。它应该解决问题并给出期望的结果。
-
可读性: 算法应该易于理解和阅读,以便其他人能够理解它的逻辑和步骤。
-
效率: 算法应该是高效的,能够在合理的时间内处理大量数据。算法的效率通常通过时间复杂度和空间复杂度来衡量。
-
鲁棒性: 算法应该能够处理不同种类的输入数据,并在输入数据不满足预期时也能正确运行。
-
可扩展性: 算法应该能够适应不同规模的问题,从小规模问题到大规模问题都能够处理。
-
优雅性: 好的算法通常是优雅的,即它们使用简单、直观的方法解决问题,而不是过于复杂或繁琐。
2.排序算法
排序算法是一类用于将一组数据按照某种规则进行排列的算法。
常见的排序算法包括但不限于以下几种:
-
冒泡排序(Bubble Sort): 通过多次交换相邻元素,每次将最大(或最小)元素“冒泡”到数组的一端,逐步完成排序。
-
选择排序(Selection Sort): 每次选择数组中最小(或最大)的元素,放到已排序部分的末尾,逐步构建有序序列。
-
插入排序(Insertion Sort): 通过构建一个有序序列,并逐个将未排序元素插入到有序序列的适当位置,来完成排序。
-
快速排序(Quick Sort): 通过选择一个基准元素,将数组分成两个子数组,左边的子数组小于基准,右边的子数组大于基准,然后对子数组递归进行排序。
-
归并排序(Merge Sort): 将数组分成两个子数组,分别对子数组进行排序,然后将已排序的子数组合并成一个有序数组。
-
堆排序(Heap Sort): 利用二叉堆的性质进行排序,将数组看作一个二叉堆,然后将最大(或最小)元素交换到堆顶,逐步构建有序堆。
-
计数排序(Counting Sort): 适用于非负整数排序,通过统计每个元素的出现次数,然后根据计数重构有序序列。
-
桶排序(Bucket Sort): 将数据划分到多个桶中,每个桶内部使用其他排序算法进行排序,最后将所有桶合并成一个有序序列。
2.1 冒泡排序
冒泡排序(Bubble Sort)通过多次交换相邻的元素,逐步将最大(或最小)的元素“冒泡”到数组的一端,从而逐步完成排序。冒泡排序的原理类似于水泡在水中上浮的过程,较大(或较小)的元素会逐渐移动到数组的右侧(或左侧)。
冒泡排序的基本思想是从数组的第一个元素开始,依次比较相邻的两个元素,如果它们的顺序不正确,就交换它们,使较大(或较小)的元素“冒泡”到正确的位置。然后,算法继续从第二个元素开始,重复同样的比较和交换操作,直到所有元素都排好序为止。
C语言代码实现如下:
void Bubble_Sort(int *array, int size) {
// 外层循环控制排序趟数
for (int i = 0; i < size -1; i++) {
// 内层循环控制每一趟排序多少次
for(int j = 0; j < size -i -1; j++) {
// 相邻元素进行比较
if(array[j] > array[j+1]) {
// 交换位置
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
冒泡排序的时间复杂度为O(n<sup>2</sup>),其中n 是待排序数组的长度。
2.2 选择排序
选择排序(Selection Sort)的基本思想是,每次从待排序的数据中选择最小(或最大)的元素,将其与序列中的第一个元素进行交换,使其成为已排序序列的一部分。
选择排序的主要步骤如下:
- 首先,在待排序序列中找到最小(或最大)的元素,记为A。
- 将A与序列中的第一个元素进行交换,将A放在已排序序列的最前面。
- 然后,在剩余的待排序序列中找到最小(或最大)的元素,记为B。
- 将B与序列中的第二个元素进行交换,将B放在已排序序列的第二个位置。
- 以此类推,直到所有元素都被放到了已排序序列的合适位置。
C语言实现代码如下:
void Selection_Sort(int array[], int size) {
for (int i = 0; i < size -1; i++) {
// keep track of the index of the minimum element
int min_index = i;
// search for min index
for (int j = i + 1; j < size; j++) {
if (array[j] < array[min_index]) {
min_index = j;
}
}
// swap
int temp = array[i];
array[i] = array[min_index];
array[min_index] = temp;
}
}
选择排序的时间复杂度为O(n<sup>2</sup>),其中n是待排序序列的长度。需要注意的是,选择排序是一种不稳定的排序算法,即相同元素的相对位置可能会在排序过程中发生改变。
2.3插入排序
插入排序(Insertion Sort)的基本思想是将一个待排序的数组(或列表)分为已排序区间和未排序区间,每次从未排序区间中选择一个元素,插入到已排序区间的正确位置,直到未排序区间为空。
插入排序的具体步骤如下:
- 从第一个元素开始,将其视为已排序区间。
- 取下一个元素,在已排序区间中从后往前扫描。
- 如果已排序区间中的元素大于待插入元素,则将该元素后移一位,继续往前扫描。
- 重复步骤3,直到找到已排序区间中的元素小于等于待插入元素,或已经到达已排序区间的起始位置。
- 将待插入元素插入到已排序区间中找到的位置后面。
- 重复步骤2-5,直到未排序区间中的所有元素都被插入到已排序区间中。
插入排序的时间复杂度为O(n<sup>2</sup>),其中n为待排序的元素个数。
C语言实现代码如下;
void Insertion_Sort(int *array, int size) {
for (int i = 0; i < size -1; i++) {
// hold the value of the element being sorted.
int key = array[i];
int j = i -1;
// Move elements of arr[0..i-1] that are greater than key,
// to one position ahead of their current position
while(j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = key;
}
}
2.4 归并排序
归并排序(Merge Sort)采用分而治之(Divide and Conquer)的思想,基本思想是将待排序的元素序列分成两部分,分别对这两部分进行排序,然后将排好序的子序列合并成一个有序的序列。它的具体步骤如下:
- 分解(Divide):将待排序的序列递归地分解成两个子序列,直到序列中只剩下一个元素。
- 合并(Merge):对两个有序的子序列进行合并操作,得到一个新的有序序列。
- 返回(Return):递归地合并子序列,直到最终将整个序列合并为一个有序序列。
归并排序的关键在于合并操作。合并操作是通过比较两个子序列的元素大小,依次选择较小的元素放入新序列中。当某一个子序列的元素已经全部放入新序列后,将另一个子序列剩余的元素直接放入新序列的后面。
归并排序的时间复杂度是O(n log(n)),其中n为待排序序列的长度。它的稳定性是由于在合并操作中,当两个相等的元素进行比较时,可以保证前面的元素先放入新序列,从而不改变相等元素的相对顺序。
C语言实现代码如下:
// Function to merge two subarrays
void merge(int array[], int left, int mid, int right)
{
// Calculate the size of subarrays
int left_size = mid - left + 1;
int right_size = right - mid;
int left_array[left_size], right_array[right_size];
// copy the data into the temporary arrays
for (int i = 0; i < left_size; i++)
{
left_array[i] = array[left + i];
}
for (int j = 0; j < right_size; j++)
{
right_array[j] = array[mid + 1 + j];
}
int i = 0; // Initial index of first subarray
int j = 0; // Initial index of second subarray
int k = left; // Initial index of merged subarray
// Merge the temp arrays back into arr[left..right]
while (i < left_size && j < right_size) {
if (left_array[i] <= right_array[j]) {
array[k] = left_array[i];
i++;
} else
{
array[k] = right_array[j];
j++;
}
k++;
}
// Copy the remaining elements of left array, if there are any
while (i < left_size)
{
array[k] = left_array[i];
i++;
k++;
}
// Copy the remaining elements of right array, if there are any
while (j < right_size)
{
array[k] = right_array[j];
j++;
k++;
}
}
//Function to sort the array
void Merge_Sort(int array[], int left, int right)
{
if (left < right)
{
// Find the middle point
int mid = left + (right - left) / 2;
// Sort first and second halves
Merge_Sort(array, left, mid);
Merge_Sort(array, mid + 1, right);
// Merge the sorted halves
merge(array, left, mid, right);
}
}
// Function to print an array
void printArray(int arr[], int size) {
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
2.5 快速排序
快速排序(Quick Sort),它同样采用了分而治之的思想。它的基本思想是选择一个基准元素,将数组分成两个子数组,使得左子数组中的元素都小于等于基准元素,右子数组中的元素都大于等于基准元素,然后递归地对子数组进行快速排序。
举例说明:
老师需要对小朋友排身高,老师先大概从小朋友中选出一个既不高也不矮的小朋友,即中位数,然后让其他比这个小朋友矮的站左边,高的站右边,然后再一次对两边的进行排身高。
主元(Pivot)在排序算法中是指被选取用于划分数组的元素。在快速排序算法中,选择一个主元并通过划分将数组分为两个子数组,其中一个子数组的所有元素小于主元,另一个子数组的所有元素大于主元。划分的过程会将主元放置到最终排序位置的正确位置上。
选择合适的主元可以影响快速排序算法的性能和效率。一个好的主元应该尽可能地将数组划分为两个近似相等大小的子数组,这样可以避免出现极端情况下的性能退化。通常的做法是选择数组的中间元素作为主元,这样可以获得较好的效果。然而,如果数组已经近乎有序,则选择中间元素可能导致性能退化,因此其他的主元选择策略也会进行优化,例如随机选择主元或者选择三个元素中的中值作为主元。
下面是快速排序的基本步骤:
-
选择一个基准元素。可以选择数组中的任意一个元素作为基准元素,通常选择第一个或最后一个元素。
-
分割。通过一次遍历,将大于基准元素的元素移到右边,将小于基准元素的元素移到左边,从而得到基准元素位置的索引。
-
递归地对左子数组和右子数组进行快速排序。重复步骤1和步骤2,直到子数组的大小为1或为空。
-
合并。合并左、基准和右三个子数组,得到最终的排序数组。
快速排序的关键在于分割过程,一般采用双指针法来实现。左指针从数组的起始位置向右移动,右指针从数组的末尾位置向左移动,不断地交换左右指针指向的元素,直到左指针和右指针相遇。最终,右指针指向的位置就是基准元素的正确位置。
快速排序的**时间复杂度为平均情况下的O(n log(n),在最坏情况下可能达到O(n<sup>2</sup>)**。
C语言实现代码如下:
// Function to swap two elements
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Function to partition the array and return the pivot index
int partition(int array[], int low, int high) {
int pivot = array[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (array[j] < pivot) {
i++;
swap(&array[i], &array[j]);
}
}
swap(&array[i + 1], &array[high]);
return (i + 1);
}
// Function to perform quicksort
void Quick_Sort(int array[], int low, int high) {
if (low < high) {
int pivot = partition(array, low, high);
Quick_Sort(array, low, pivot - 1);
Quick_Sort(array, pivot + 1, high);
}
}
2.6 计数排序
计数排序(Counting Sort)是一种非比较排序算法,它通过统计数组中元素出现的次数,然后根据次数重新构建有序的数组。
计数排序的基本思想是,首先找出数组中的最大值,创建一个计数数组,数组的长度为最大值加一。然后遍历原始数组,将每个元素在计数数组中对应的位置上的值加一。接着,根据计数数组的值依次将原始数组中的元素放回到有序数组中,每放一个元素就将计数数组对应的位置的值减一。最后得到的有序数组即为计数排序的结果。
下面以一个简单的例子来说明计数排序的过程:
假设待排序数组为 [4, 3, 2, 1, 4, 3, 2, 1]。
-
找出数组中的最大值,得到最大值为 4。
-
创建一个计数数组 count,长度为最大值加一,即长度为 5,全部初始化为 0。
-
遍历原始数组,统计每个元素出现的次数,并在 count 数组中进行累加。遍历过程如下:
- 数组元素为 4,count[4] 加一,count 变为 [0, 0, 0, 0, 1]。
- 数组元素为 3,count[3] 加一,count 变为 [0, 0, 0, 1, 1]。
- 数组元素为 2,count[2] 加一,count 变为 [0, 0, 1, 1, 1]。
- 数组元素为 1,count[1] 加一,count 变为 [0, 1, 1, 1, 1]。
- 数组元素为 4,count[4] 加一,count 变为 [0, 1, 1, 1, 2]。
- 数组元素为 3,count[3] 加一,count 变为 [0, 1, 1, 2, 2]。
- 数组元素为 2,count[2] 加一,count 变为 [0, 1, 2, 2, 2]。
- 数组元素为 1,count[1] 加一,count 变为 [0, 2, 2, 2, 2]。
-
根据 count 数组的值,重新构建有序数组。将原始数组中的元素根据其在 count 数组中的值依次放回有序数组。有序数组如下:
- 依次放入值为 1 的元素:[1]
- 依次放入值为 1 的元素:[1, 1]
- 依次放入值为 2 的元素:[1, 1, 2]
- 依次放入值为 2 的元素:[1, 1, 2, 2]
- 依次放入值为 2 的元素:[1, 1, 2, 2, 2]
- 依次放入值为 1 的元素:[1, 1, 2, 2, 2, 4]
- 依次放入值为 1 的元素:[1, 1, 2, 2, 2, 4, 4]
- 依次放入值为 0 的元素:[1, 1, 2, 2, 2, 4, 4]
最终的有序数组为 [1, 1, 2, 2, 2, 4, 4],即为计数排序的结果。
计数排序的时间复杂度为 O(n+k),其中 n 表示数组的大小,k 表示数组中的元素范围。
C语言实现代码如下:
void Counting_Sort(int array[], int n) {
int i, max = array[0], *countArr, *sortedArr;
// Find the maximum element in the array
for (i = 1; i < n; i++) {
if (array[i] > max) {
max = array[i];
}
}
// Create a count array with size max+1 and initialize all elements to 0
countArr = (int *)calloc(max + 1, sizeof(int));
// Count the occurrences of each element in the original array
for (i = 0; i < n; i++) {
countArr[array[i]]++;
}
// Modify the count array, so that each element at index i contains the count of the elements before it
for (i = 1; i <= max; i++) {
countArr[i] += countArr[i - 1];
}
// Create a new sorted array
sortedArr = (int *)malloc(n * sizeof(int));
// Place each element in the original array at its correct position in the sorted array
for (i = n - 1; i >= 0; i--) {
sortedArr[countArr[array[i]] - 1] = array[i];
countArr[array[i]]--;
}
// Copy the sorted array back to the original array
for (i = 0; i < n; i++) {
array[i] = sortedArr[i];
}
// Free dynamically allocated memory
free(countArr);
free(sortedArr);
}
2.7 桶排序
桶排序(Bucket Sort)将数组划分为若干个桶(或称为容器),然后将待排序元素分配到不同的桶中。每个桶中的元素再分别进行排序,最后将所有的桶合并,得到有序的结果。
桶排序的基本思想是根据待排序元素的分布特点将其均匀地分散到不同的桶中。每个桶可以使用不同的排序算法对其内部的元素进行排序,也可以继续递归地使用桶排序。
具体步骤如下:
- 初始化一个足够数量的空桶。
- 遍历待排序的数组,将每个元素放入对应的桶中。
- 对每个桶中的元素进行排序,可以使用快速排序、插入排序等排序算法。
- 将所有桶中的元素按照顺序依次取出,组成有序的结果数组。
桶排序的时间复杂度取决于桶的数量和元素在每个桶中的分布情况。如果元素能够均匀地分布在不同的桶中,则桶排序的时间复杂度接近线性的 O(n)。但是,如果大部分元素都被分配到少数几个桶中,就可能会导致桶排序的效率下降。
桶排序适用于待排序元素的范围较小,并且元素分布比较均匀的情况。它在外部排序中也有应用,可以处理大规模数据的排序问题。
C语言实现代码如下:
// Function to implement a simple bucket sort algorithm
void bucketSort(int array[], int n) {
// Create an array of empty buckets
int *buckets = (int *)malloc(n * sizeof(int));
// Initialize all elements in buckets to 0
for (int i = 0; i < n; i++) {
buckets[i] = 0;
}
// Increment the count in the corresponding bucket for each element in the input array
for (int i = 0; i < n; i++) {
buckets[array[i]]++;
}
// Output sorted elements from each bucket
for (int i = 0, j = 0; i < n; i++) {
// Repeat the bucket value (i) based on its count
while ((buckets[i]--) > 0) {
array[j++] = i;
}
}
free(buckets);
}
2.8 基数排序
基数排序(Radix Sort)是一种非比较性的排序算法。它将元素按照每个位上的数字进行排序,从低位到高位依次进行,最终得到有序序列。基数排序可以分为 LSD(Least Significant Digit)和 MSD(Most Significant Digit)两种方式。
在LSD的基数排序中,首先从最低位开始,按照该位的数字将元素分配到相应的桶中,然后依次按照下一位的数字进行分配,直到最高位,最终排序完成。每次分配到桶中后,可以使用稳定的排序算法(如计数排序或桶排序)对桶中的元素进行排序。
对于MSD的基数排序,首先对整个待排序的序列按照最高位进行排序分配,然后对每个桶中的元素再按照次高位进行排序分配,直到按照最低位排序分配完成。在每次分配到桶中后,如果桶中的元素数量较少,可以使用插入排序或者快速排序等算法进行排序。
基数排序的时间复杂度为O(d*(n+b)),其中d为元素的最大位数,b为基数范围,n为元素个数。
基数排序可以适用于非负整数、字符串等类型的数据排序。它相对于其他比较性排序算法,例如快速排序、归并排序,基数排序的特点是稳定的排序结果。但是,对于待排序元素的位数较少,且元素较多时,基数排序的空间复杂度较高。
C语言实现代码如下:
// Find the maximum element in the array
int getMax(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
// Perform counting sort based on the digit represented by exp
void Counting_Sort(int arr[], int n, int exp) {
int output[n]; // Output array
int count[10] = {0}; // Initialize count array with zeros
// Store count of occurrences in count[]
for (int i = 0; i < n; i++) {
count[(arr[i] / exp) % 10]++;
}
// Change count[i] so that count[i] now contains
// the actual position of this digit in output[]
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// Build the output array
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
// Copy the output array to arr[]
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}
// Radix Sort function
void Radix_Sort(int arr[], int n) {
// Find the maximum element in the array to determine the number of digits
int max = getMax(arr, n);
// Perform counting sort for every digit, starting from the least significant to the most significant
for (int exp = 1; max / exp > 0; exp *= 10) {
Counting_Sort(arr, n, exp);
}
}
各个排序算法的动画演示可以参考:visualising data structures and algorithms through animation
标签:count,int,元素,基础,算法,数组,array,排序 From: https://blog.51cto.com/LowellHere/8972628