1. Toy模板网首页
  2. > Toy博客

数据结构——各种常见算法的实现方法和思路

9月前 作者：C++代码之家 分类：Toy博客 阅读(36) 违法举报

这篇具有很好参考价值的文章主要介绍了数据结构——各种常见算法的实现方法和思路。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。


数据结构——各种常见算法的实现方法和思路,算法,数据结构,java,c++

常见的排序算法

类型

数据结构——各种常见算法的实现方法和思路,算法,数据结构,java,c++

复杂度和稳定性

数据结构的复杂度和稳定性是评价数据结构优劣的两个方面，复杂度主要关注数据结构在执行操作时所需的时间和空间资源消耗，而稳定性主要关注数据结构在执行操作时是否能够保证原有数据的相对位置不变。
数据结构——各种常见算法的实现方法和思路,算法,数据结构,java,c++

1.冒泡排序

数据结构——各种常见算法的实现方法和思路,算法,数据结构,java,c++
数据结构——各种常见算法的实现方法和思路,算法,数据结构,java,c++

这是一个冒泡排序算法的实现，它可以对一个整型数组按照从大到小的顺序进行排序。

算法的基本思想是通过不断比较相邻的元素并交换它们的位置，将较大的元素逐渐“冒泡”到数组的顶端。具体来说，该算法通过双重循环实现：外层循环控制比较的轮数，内层循环负责相邻元素的比较和交换操作。在每一轮比较中，如果当前元素比它后面的元素小，就交换它们的位置，使得较大的元素逐渐向数组的前部移动。

该算法的时间复杂度为O(n^2)，其中n为数组的长度。虽然它的时间复杂度较高，但是它的实现简单、容易理解，对于小规模的数据排序来说还是比较实用的。

//从小到大
void BubbleSort1(int* a, int n)
{
	for (int i = 0; i < n-1; i++)
	{
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (a[j] > a[j + 1])
			{
				int temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
			}
		}
	}
}

这也是一个冒泡排序算法的实现，可以对一个整型数组按照从小到大的顺序进行排序。

与上一个算法相比，该算法的唯一区别在于内层循环中比较的方式。在该算法中，如果当前元素比它后面的元素大，就交换它们的位置，使得较小的元素逐渐向数组的前部移动。

该算法的时间复杂度同样为O(n^2)，其中n为数组的长度。由于冒泡排序算法的优化空间比较有限，因此它的时间复杂度较高，不适合用于大规模数据的排序。

//从大到小
void BubbleSort2(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (a[j] < a[j + 1])
			{
				int temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
			}
		}
	}
}

2.直接插入排序

数据结构——各种常见算法的实现方法和思路,算法,数据结构,java,c++
插入排序是一种简单直观的排序算法，其核心思想是将未排序的元素逐个插入到已排序的序列中，以便生成一个新的有序序列。插入排序的过程类似于打扑克牌时的整理牌的方法，即将一张牌插入到已经排好序的牌中的适当位置。

插入排序的基本思路是从第二个元素开始，逐个将元素插入到前面已经排好序的子序列中。具体而言，对于第 i 个元素，我们将其与前面的元素逐个比较，找到第一个比它小的元素，然后将它插入到这个元素后面，即可保证前 i 个元素已经排好序。这个过程不断重复，直到整个序列都有序为止。

插入排序的时间复杂度为 O(n^2)，它的性能与输入数据的初始顺序有关。如果输入数据已经接近有序，那么插入排序的效率会比较高，因为它只需要进行少量的比较和移动操作。但如果输入数据的顺序比较随机，那么插入排序的效率会比较低，因为它需要进行大量的比较和移动操作。


// 插入排序
void InsertSort(int* a, int n)
{
     //从第2个元素开始插入排序
    for (int i = 1; i < n; i++)
    {
        int end = i - 1;  // 已排序序列的最后一个元素的下标
        int tmp = a[i];     // 待插入的元素
         //将待插入的元素与已排序的元素从后往前依次比较
        while (end >= 0)
        {
            if (tmp < a[end])
            {
                a[end + 1] = a[end];  // 如果比已排序的元素小，则将已排序的元素后移一位
                end--;
            }
            else
            {
                break;  // 如果找到一个比待插入元素小的位置，则退出循环
            }
        }
        a[end + 1] = tmp;  // 将待插入的元素插入到已排序的序列中
    }
}

3.希尔排序

数据结构——各种常见算法的实现方法和思路,算法,数据结构,java,c++
希尔排序（Shell Sort）是插入排序的一种改进版本，也称为缩小增量排序（diminishing increment sort）。它通过将待排序的序列分割成若干个子序列，对每个子序列进行插入排序，从而实现对整个序列的排序。

希尔排序的核心思想是将相距某个“增量”的元素组成一个子序列，对每个子序列进行插入排序，使得整个序列在增量不断缩小的情况下逐步变得有序。最后当增量为1时，整个序列就变成了一个有序序列。

具体实现中，希尔排序先将待排序的元素按照一定的增量分成若干个子序列，对每个子序列进行插入排序。然后，逐渐减小增量，继续对子序列进行插入排序，直到增量为1时，完成最后一次排序，整个序列就变成了有序序列。

希尔排序的时间复杂度为 O(n log n) 到 O(n^2)，具体取决于增量的选择和子序列的划分方式。希尔排序的优点是它的实现比较简单，只需要对插入排序进行一些改进即可。缺点是增量序列的选择比较困难，不同的增量序列对性能的影响也比较大。

//希尔排序
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap /= 2;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[i + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

4.简单选择排序

数据结构——各种常见算法的实现方法和思路,算法,数据结构,java,c++

选择排序（Selection Sort）是一种简单直观的排序算法，其核心思想是在未排序序列中选择最小（或最大）的元素，放到已排序序列的末尾，直到所有元素都排完为止。

具体实现中，选择排序从未排序序列中找到最小（或最大）的元素，然后将它与未排序序列的第一个元素交换，这样就可以把该元素放到已排序序列的末尾。然后，在剩余的未排序序列中继续找到最小（或最大）的元素，重复上述操作，直到所有元素都排完为止。

选择排序的时间复杂度为 O(n^2)，它的性能比冒泡排序略好，但比插入排序差。选择排序的优点是它的实现比较简单，只需要进行 n-1 次比较和 n 次交换，因此在某些情况下它的性能可能比其他排序算法更好。缺点是它的时间复杂度比较高，不适合对大规模数据进行排序。

方法1：双向遍历选择排序

//交换
Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
void SelectSort1(int* a, int n) 
{
	int left = 0;
	int right = n - 1;
	while (left < right)
	{
		int max = left, mini = left;
		for (int i = left + 1; i <= right; i++)
		{
			
			if (a[i] < a[mini])
			{
				mini = i;
			}
			if (a[i] > a[max])
			{
				max = i;
			}
		}
		Swap(&a[left], &a[mini]);
		if (left == max)
		{
			max = mini;
		}
		Swap(&a[right], &a[max]);
		++left;
		--right;
	}
}

方法2：单向遍历选择排序

//交换
void Swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

void SelectSort2(int* a, int n)
{
	int min,i,j;
	for (int i = 0; i < n - 1; i++)
	{
		min = i;
		for (int j = i + 1; j < n; j++)
		{
			if (a[j] < a[min])
			{
				min = j;
			}
		}
		int temp = a[min];
		a[min] = a[i];
		a[i] = temp;
    }
}

5.归并排序

数据结构——各种常见算法的实现方法和思路,算法,数据结构,java,c++

方法1：递归

这是一种基于分治的排序算法 - 归并排序。
思路:

  1. 将数组分成两个子数组,递归调用排序子数组
  2. 将两个有序子数组合并成一个有序数组
void _MergeSort(int* a, int begin, int end, int* tmp)
{
	if (begin>=end)
	{
		return;
	}
	int mid = (begin + end) / 2;
	//[begin,mid] [mid+1,end]，子区间递归排序
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid + 1, end, tmp);
	//[begin,mid] [mid+1,end]归并
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}
	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
void MergeSort(int* a, int n)
{
	
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("mallco fail");
		return;
	}
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
}

方法2：非递归

思路：

  1. 使用一个gap进行划分,从1开始扩大gap,每次将相邻gap大小的两个子数组合并
  2. 合并相邻gap大小的两个子数组的方法和递归版本是一样的
  3. 每次将gap * 2,进行下一轮划分和合并
  4. 重复此过程,直到gap >= n,排序完成
//非递归
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("mallco fail");
		return;
	}
	int gap = 1;
	while (gap<n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			//[begin1,end1][begin2,end2]
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			if (end1 >= n || begin2 >= n)
			{
				break;
			}
			if (end2 >= n)
			{
				end2 = n - 1;
			}
			int j = i;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}
			//归并一部分拷贝一部分
			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
		}
		gap *= 2;
	}
	free(tmp);
}

6.快速排序

数据结构——各种常见算法的实现方法和思路,算法,数据结构,java,c++

方法1：随机取keyi

思路：

  1. 选择一个基准元素(使用随机数随机选择一个元素)
  2. 将所有比基准元素小的元素移动到其左边,所有比基准元素大的元素移动到其右边
  3. 对基准元素的左右两边重复第一步和第二步,直到全部排序完成
void Swap(int* p1, int* p2)
{
	int temp = *p1;
	*p1 = *p2;
	*p2 = temp;
}
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;
	int begin = left;
	int end = right;
	//随机选key
	int randi = left + (rand() % (right - left));
	Swap(&a[left], &a[randi]);
	int keyi = left;
	while (left < right)
	{
		//右边找小
		while (left < right && a[right] >= a[keyi])
			--right;
		//左边找大
		while (left<right && a[left]>a[keyi])
			++left;
		Swap(&a[left], &a[right]);
	}
}

方法2：三数取中

思路：

  1. 首先利用中位数作为基准值,选择最稳定的基准值。
  2. 获取三个数的中位数:
    如果a[left]<a[mid],那么：如果a[mid]<a[right], mid是中位数，否则比较a[left] 和 a[right],较大值是中位数
  3. 将中位数与第一个元素交换,作为基准值
  4. 其他部分与普通快速排序相同
void Swap(int* p1, int* p2)
{
	int temp = *p1;
	*p1 = *p2;
	*p2 = temp;
}
int GetMidNumi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		} 
		else
		{
			return right;
		}
	}
	else//a[left]>a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
void QuickSort2(int* a, int left, int right)
{
	if (left >= right)
		return;
	int begin = left;
	int end = right;
	int midi = GetMidNumi(a, left, right);
	if (midi != left)
	{
		Swap(&a[midi], &a[left]);
	}
	int keyi = left;
	while (left < right)
	{
		//右边找小
		while (left < right && a[right] >= a[keyi])
			--right;
		//左边找大
		while (left<right && a[left]<=a[keyi])
			++left;
		Swap(&a[left], &a[right]);
	}
	Swap(&a[keyi], &a[left]);
	keyi = left;
	QuickSort2(a, begin, keyi - 1);
	QuickSort2(a, keyi + 1, end);
}

方法3：挖坑法

数据结构——各种常见算法的实现方法和思路,算法,数据结构,java,c++

思路：

  1. 使用 begin 和 end 表示子数组范围
  2. key 记录基准值,hole 记录待填充位置
  3. 把 left 和 right 指针分别指向 begin 和 end
  4. while 循环：右边第一个小于等于 key 的元素,记录其索引到 hole, right，左边第一个大于 key 的元素,记录其索引到 hole,left++
  5. hole 位置填充 key 值
  6. 对基准值左右两侧的子数组递归调用快速排序
void QuickSort3(int* a, int left, int right)
{
	if (left >= right)
		return;
	int begin = left;
	int end = right;
	int key = a[left];
	int hole = left;
	while (left < right)
	{
		//右边找小
		while (left < right && a[right] >= key)
			--right;
		a[hole] = a[right];
		hole = right;
		//左边找大
		while (left < right && a[left] <= key)
			++left;
		a[hole] = a[left];
		hole = left;
	}
	a[hole] = key;
	QuickSort3(a, begin, hole - 1);
	QuickSort3(a, hole+ 1, end);
}

方法4：前后指针法

数据结构——各种常见算法的实现方法和思路,算法,数据结构,java,c++

快速排序的前后指针法（也称为双指针法）是一种常见的划分方式。它的基本思想是，将整个序列分为小于等于主元的左半部分和大于主元的右半部分，然后递归地对左右两个部分进行排序。

思路：

  1. 依然使用left、right指针和基准值pivot。
  2. 额外引入一个prev指针,记录小于pivot的最后一个元素的位置。
  3. 当遍历到一个元素时：如果元素 < pivot,将其与prev指向的元素交换,prev后移 1 位，如果元素 = pivot,直接略过，如果元素 > pivot,继续遍历
  4. 最终prev指向的位置,就是pivot的正确位置。
int QuickSort4(int* a, int left, int right)
{
	int midi = GetMidNumi(a, left, right);
	if (midi != left)
	{
		Swap(&a[midi], &a[left]);
	}
	int keyi =left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] <a[keyi] && ++prev != cur)
			Swap(&a[cur], &a[prev]);
		++cur;
	}
	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	return keyi;
}

方法5:非递归

这里使用了一个栈来模拟递归过程。首先将整个序列的左右端点入栈，之后每次取出栈顶的左右端点，进行一次划分并将新的左右端点入栈，直到栈为空为止。在划分函数中使用双指针法将小于等于主元的元素放在左边，大于主元的元素放在右边，最后把主元放在中间，并返回主元的下标。

需要注意的是，这里使用了一个结构体 Range 来表示左右端点的范围，这样可以方便地把左右端点打包在一起并压入栈中。

#include <stdio.h>
#define MAX_SIZE 100
typedef struct {
    int l;
    int r;
} Range;

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int arr[], int l, int r) {
    int pivot = arr[l];
    while (l < r) {
        while (l < r && arr[r] >= pivot) r--;
        arr[l] = arr[r];
        while (l < r && arr[l] <= pivot) l++;
        arr[r] = arr[l];
    }
    arr[l] = pivot;
    return l;
}

void quickSort(int arr[], int n) {
    Range stack[MAX_SIZE];
    int top = -1;
    stack[++top] = (Range){ 0, n - 1 };
    while (top >= 0) {
        Range range = stack[top--];
        if (range.l >= range.r) continue;
        int p = partition(arr, range.l, range.r);
        stack[++top] = (Range){ range.l, p - 1 };
        stack[++top] = (Range){ p + 1, range.r };
    }
}

int main() {
    int arr[] = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

方法6：三路划分

数据结构——各种常见算法的实现方法和思路,算法,数据结构,java,c++

思路：

  1. 跟key相等的值，往后推
  2. 比key小的甩到左边
  3. 比key大的甩到右边
  4. 跟key相等的就在中间
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
void quicksort(int arr[], int low, int high) {
    if (low >= high) {
        return;
    }
    // 选取第一个元素为基准值
    int pivot = arr[low];
    // lt指向小于基准值的部分的最后一个元素
    int lt = low;
    // gt指向大于基准值的部分的第一个元素
    int gt = high;
    // i指向当前处理的元素
    int i = low + 1;
    // 三路划分
    while (i <= gt) {
        if (arr[i] < pivot) {
            // 将小于基准值的元素交换到lt部分
            swap(&arr[i], &arr[lt]);
            lt++;
            i++;
        }
        else if (arr[i] > pivot) {
            // 将大于基准值的元素交换到gt部分
            swap(&arr[i], &arr[gt]);
            gt--;
        }
        else {
            // 相等的元素直接跳过
            i++;
        }
    }
    // 递归排序小于基准值的部分
    quicksort(arr, low, lt - 1);
    // 递归排序大于基准值的部分
    quicksort(arr, gt + 1, high);
}
int main() {
    int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    quicksort(arr, 0,n-1);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

7.堆排序

数据结构——各种常见算法的实现方法和思路,算法,数据结构,java,c++

思路：

使用 maxHeapify() 函数维护最大堆的属性。

使用 n/2 - 1 作为起始索引,逐层地将数组调整为最大堆。

排序部分:

  1. 将堆顶元素(最大元素)与末尾元素交换
  2. 缩小堆的范围(n范围减1),再次调用 maxHeapify() 函数,维护最大堆的属性。
  3. 重复上两步,直到堆范围为0。
// 交换函数 
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void maxHeapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2*i + 1;
    int right = 2*i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        maxHeapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    // 构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--)
        maxHeapify(arr, n, i);

    // 排序
    for (int i = n - 1; i >= 0; i--) {
        swap(&arr[0], &arr[i]); // 将最大值交换到数组末尾
        maxHeapify(arr, i, 0);
    }
}

int main() {
    int arr[] = { 12, 11, 13, 5, 6, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);

    heapSort(arr, n);

    // 打印排序后的数组
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}

8.计数排序

数据结构——各种常见算法的实现方法和思路,算法,数据结构,java,c++

思路：

  1. 扫描一次给定的数组,找到最大元素和最小元素
  2. 根据最大元素和最小元素,计算出需要多大的空间用于排序
  3. 创建计数数组 countA,长度为范围(max - min + 1)
  4. 遍历给定数组,对于每个元素 a[i],计数数组 countA[a[i] - min] 加 1
  5. 对计数数组进行累加求和,使每个元素表示当前元素及之前所有元素的个数
  6. 遍历给定数组,将元素放在正确位置上
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
void CountSort(int* a, int n)
{
	int max = a[0], min = a[0];
	for (int i = 1; i < n; i++)
	{
		if (a[i] > max)
		{
			max = a[i];
		}
		if (a[i] < min)
		{
			min = a[i];
		}
	}
	int range = max - min + 1;
	int* countA = (int*)malloc(sizeof(int) * range);
	if (countA == NULL)
	{
		perror("malloc fail");
		return;
	}
	memset(countA, 0, sizeof(int) * range);

	//计数
	for (int i = 0; i < n; i++)
	{
		countA[a[i] - min]++;
	}

	//排序
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (countA[i]--)
		{
			a[j++] = i + min;
		}
	}
	free(countA);
}
int main()
{
	int arr[] = { 2,3,5,6,7,3,2,5,5,5,9,200 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	CountSort(arr, sz);
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

9.基数排序

数据结构——各种常见算法的实现方法和思路,算法,数据结构,java,c++

思路：

  1. 对数组按照最低阶(个位数)进行分配,然后收集。
  2. 再按照次低阶(十位数)分配和收集,依次类推到最高阶。
  3. 每次分配、收集都会让数组更加有序。

具体实现：

  1. 定义最大基数为 RADIX(10),一个辅助队列组 Q[]
  2. Getkey() 函数获取元素 value 在指定位数 k 的值
  3. Distribute() 函数将数组中元素按照 k 位分配到相应的队列中
  4. Collect() 函数收集队列中的元素,反向填充数组
  5. RadixSort() 函数依次分配、收集 K次,K为指定位数
#include<iostream>
#include<stdio.h>
#include<queue>
using namespace std;
#define K 3
#define RADIX 10
queue<int> Q[RADIX];

int Getkey(int value, int k)
{
	int key = 0;
	while (k >= 0)
	{
		key = value % 10;
		value /= 10;
		k--;
	}
	return key;
}
//分发数据
void  Distribute(int arr[], int left, int right, int k)
{
	for (int i = left; i < right; i++)
	{
		int key = Getkey(arr[i],k);
		Q[key].push(arr[i]);
	}
}
//回收数据
void Collect(int arr[])
{
	int k = 0;
	for (int i = 0; i < RADIX; i++)
	{
		while (!Q[i].empty())
		{
			arr[k++] = Q[i].front();
			Q[i].pop();
		}
	}
}
void RadixSort(int* arr, int left, int right)
{
	for (int i = 0; i < K; i++)
	{
		//分发数据
		Distribute(arr, left, right, i);
		//回收数据
		Collect(arr);
	}
}

int main()
{
	int arr[] = { 278,109,63,930,589,184,505,269,8,83 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	//基数排序
	RadixSort(arr, 0, sz);
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

9.桶排序

数据结构——各种常见算法的实现方法和思路,算法,数据结构,java,c++

桶排序是一种线性排序算法，它的基本思想是将待排序的元素分到不同的桶中，每个桶内的元素再分别使用其他排序算法进行排序，最后合并所有桶中的元素即可得到有序序列。桶排序的时间复杂度为 O(n)，但是它的空间复杂度较高，需要额外的空间来存储桶。文章来源地址https://www.toymoban.com/news/detail-562613.html

#include <stdio.h>
#include <stdlib.h>

// 桶排序
void bucket_sort(int arr[], int n) {
    int max_num = arr[0];
    int min_num = arr[0];
    int i, j, k;
    for (i = 1; i < n; i++) {
        if (arr[i] > max_num) {
            max_num = arr[i];
        }
        if (arr[i] < min_num) {
            min_num = arr[i];
        }
    }

    int bucket_size = (max_num - min_num) / n + 1;
    int bucket_count = (max_num - min_num) / bucket_size + 1;
    int **buckets = malloc(sizeof(int*) * bucket_count);
    for (i = 0; i < bucket_count; i++) {
        buckets[i] = malloc(sizeof(int) * n);
    }
    int *count = malloc(sizeof(int) * bucket_count);

    for (i = 0; i < bucket_count; i++) {
        count[i] = 0;
    }
    for (i = 0; i < n; i++) {
        int index = (arr[i] - min_num) / bucket_size;
        buckets[index][count[index]] = arr[i];
        count[index]++;
    }

    k = 0;
    for (i = 0; i < bucket_count; i++) {
        for (j = 0; j < count[i]; j++) {
            arr[k] = buckets[i][j];
            k++;
        }
    }

    for (i = 0; i < bucket_count; i++) {
        free(buckets[i]);
    }
    free(buckets);
    free(count);
}

// 测试桶排序
int main() {
    int arr[] = {5, 2, 8, 3, 9, 6};
    int n = sizeof(arr) / sizeof(int);
    bucket_sort(arr, n);
    printf("排序后的结果为：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

到了这里，关于数据结构——各种常见算法的实现方法和思路的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】快速排序的三种实现方法

    【数据结构与算法】快速排序的三种实现方法

      目录 一.基本思想 二.Hoare法 动态演示 三.挖坑法 动态演示 四.前后指针法 动态演示 五.快速排序优化 随机下标交换法 三路取中法 六.快速排序的特性 任取待排序元素序列中的某元素作为 基准值 ，按照该排序码将待排序集合 分割成两子序列 ， 左子序列中所有元素均小于基

    2023年04月09日
    浏览(64)
  • 【数据结构】常见的排序算法

    【数据结构】常见的排序算法

    常见的七大排序算法： 最好的情况是O(n)，数组为升序 最坏的情况是O(n 2 )，数组为降序 元素集合越接近有序，直接插入排序算法的时间效率越高 时间复杂度：O(N^2) 空间复杂度：O(1)，它是一种稳定的排序算法 稳定性：稳定 针对直接插入排序中，当数组属于降序时，时间复杂

    2024年02月14日
    浏览(39)

  • 数据结构与算法常见题

    1. 字符串变形 描述 ： 对于一个长度为 n 字符串，我们需要对它做一些变形。 首先这个字符串中包含着一些空格，就像\\\"Hello World\\\"一样，然后我们要做的是把这个字符串中由空格隔开的单词反序，同时反转每个字符的大小写。 示例1 输入： “This is a sample”,16 返回值： “SAM

    2024年02月14日
    浏览(36)
  • 数据结构-常见的排序算法

    数据结构-常见的排序算法

    目录 排序的概念及其运用 排序的概念 常见的排序算法 常见排序算法的实现 插入排序 插入排序 希尔排序(缩小增量排序) 选择排序 直接选择排序 堆排序 交换排序 冒泡排序 快速排序 归并排序 非比较排序 排序算法复杂度及稳定性分析 排序 ：所谓排序，就是按照某个或者某

    2024年03月12日
    浏览(48)
  • 数据结构之常见排序算法

    数据结构之常见排序算法

    排序：就是使一串记录，按照其中的某个或某些的大小，递增或递减的排列起来的操作。 稳定性：假设一组序列中，有两个相同的元素，在排序之后，两个相同元素的前后顺序颠倒了，说明这个排序算法是不稳定的，反之。 思路：把待排序的记录按其关键码值的大小

    2024年02月11日
    浏览(34)
  • 【数据结构】 常见的八大排序算法

    【数据结构】 常见的八大排序算法

    排序有 内部排序和外部排序 ，内部排序是数据记录在内存中进行排序，这里八大排序就是内部排序，指直接插入，希尔，选择，堆排，冒泡，快排，归并，计数。 下面让我们来共同学习这八大排序吧！🤗🤗🤗 什么是外部排序： 外排序是数据量较大,内存放不下,数据放到外

    2024年02月12日
    浏览(111)
  • 【数据结构】——常见排序算法（演示图+代码+算法分析）

    【数据结构】——常见排序算法（演示图+代码+算法分析）

    目录 1.  常见排序算法 1.2 稳定性 2.  常见排序算法的实现 2.1 插入排序 2.1.1基本思想 2.1.2代码 2.1.4算法分析  2.2 希尔排序 2.2.1基本思想 2.2.2代码 2.2.3演示图  2.2.4算法分析 2.3 选择排序 2.3.1基本思想 2.3.2代码 2.3.3演示图 2.3.4算法分析 2.4 堆排序 2.4.1基本思想  2.4.2代码 2.4.3演示

    2024年02月11日
    浏览(72)
  • 【数据结构之树】初阶数据结构之树的实现及其各种方式(上)

    【数据结构之树】初阶数据结构之树的实现及其各种方式(上)

    👻作者简介：M malloc，致力于成为嵌入式大牛的男人 👻专栏简介：本文收录于 初阶数据结构 ，本专栏主要内容讲述了初阶的数据结构，如顺序表，链表，栈，队列等等，专为小白打造的文章专栏。 👻相关专栏推荐：LeetCode刷题集，C语言每日一题。 本篇文章我将详细的讲解

    2024年02月17日
    浏览(49)
  • 数据结构：常见算法的时间复杂度汇总

    数据结构：常见算法的时间复杂度汇总

    目录 顺序表 链表 二叉树 图（V是顶点个数，E是边的条数） 1.存储空间： 2.BFS和DFS的时间复杂度 3.最小生成树时间复杂度 4.最短路径时间复杂度 查找的平均查找长度（ASL）  排序 算法操作 时间复杂度 空间复杂度 描述 插入 O（n） 需要移动元素，移动结点的平均次数n/2 删除

    2024年02月10日
    浏览(56)
  • 【数据结构】常见排序算法——常见排序介绍、插入排序、直接插入排序、希尔排序

    【数据结构】常见排序算法——常见排序介绍、插入排序、直接插入排序、希尔排序

      在计算机科学中，排序是将一组数据按照指定的顺序排列的过程。排序算法由于执行效率的不同可以分为多种不同的算法。   通常情况下，排序算法可以分为两类，即 内部排序和外部排序 。内部排序是指数据全部加载到内存中进行排序，适用于数据量较小的情况，而

    2024年02月08日
    浏览(63)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包