2025年王道中数据结构的排序算法

科技前沿 • 2025-03-14 23:50 • 阅读 30

大家好，我是讯享网，很高兴认识大家。

插入排序：
1.1. 希尔排序：

void ShellSort(ElemType A[],int n) { 
    int i,j,dk; for (dk = n / 2; dk >= 1; dk = dk / 2) for (i = dk + 1; i <= n; ++i) if (A[i]<A[i-dk]) { 
    A[0] = A[i]; for (j = i - dk; j > 0 && A[0] < A[j]; j -= dk) A[j + dk] = A[j]; A[j + dk] = A[0]; } }

讯享网

1.2. 直接插入排序：

讯享网/*直接插入排序*/ void InsertSort(ElemType A[], int n) { 
    int i, j; for (i = 2; i <= n; ++i) { 
    if (A[i] < A[i - 1]) { 
    A[0] = A[i]; for (j = i - 1; A[0] < A[j]; --j) A[j + 1] = A[j]; A[j + 1] = A[0]; } } }

1.3. 折半插入排序：

/*折半插入排序*/ void BinarySort(ElemType A[], int n) { 
    int i,j,low , high ,mid; for (i = 2; i <= n; ++i) { 
    A[0] = A[i]; low = 1; high = i - 1; while (low<high) { 
    mid = (low + high) / 2; if (A[mid] > A[0]) high = mid - 1; else low = mid + 1; } for (j= i-1; j >= high+1; --j) A[j + 1] = A[j]; A[high + 1] = A[0]; } }

交换排序：
2.1. 冒泡排序：

讯享网/*冒泡排序*/ void InsertSort(ElemType A[],int n) { 
    int i,j,temp; bool flag; for (i = 0; i <= n; ++i) { 
    flag = false; for (j = n - 1; j > i; --j) if (A[j - 1] > A[j]) { 
    temp = A[j]; A[j] = A[j - 1]; A[j - 1] = temp; flag = true; } if (flag == false) return; } }

2.2. 快速排序：

讯享网

int Partition(ElemType A[], int low, int high) { 
    int pivot = A[low]; while (low<high) { 
    while (low < high&&A[high] >= pivot) --high; A[low] = A[high]; while (low < high&&A[low] <= pivot) ++low; A[high] = A[low]; } A[low] = pivot; return low; } /*快速排序*/ void QuickSort(ElemType A[],int low,int high) { 
    if (low < high) { 
    int pivotops = Partition(A, low, high); QuickSort(A, low, pivotops - 1); QuickSort(A, pivotops + 1, high); } }

选择排序：
3.1. 简单选择排序：

讯享网/*简单选择排序*/ void SelectSort(ElemType A[], int n) { 
    int i,j,min,x; for (i = 0; i < n - 1; ++i) { 
    min = i; for (j = i + 1; j < n; j++){ 
    if (A[j] < A[min]) min = j; } //如果不相同就交换两个的位置再进行选最小的 if (min != i) { 
    x = A[i]; A[i] = A[min]; A[min] = x; } } }

3.2. 堆排序：

void AdjustDown(ElemType A[], int k, int len) { 
    int i; A[0] = A[k];//A[0]暂存 for (i = 2 * k; i <= len; i *= 2) { 
    if (i < len&&A[i] < A[i + 1]) i++; if (A[0] >= A[i]) break; else { 
    A[k] = A[i]; k = i; } } A[k] = A[0]; } /*建立大根堆*/ void BuildMaxHeap(ElemType A[], int len) { 
    for (int i = len / 2; i > 0; --i) { 
    AdjustDown(A, i, len); } } /*堆排序*/ void HeapSort(ElemType A[], int len) { 
    ElemType x; int i; BuildMaxHeap(A, N - 1); for (i = len; i > 1;--i) { 
    x = A[i]; A[i] = A[1]; A[1] = x; AdjustDown(A, 1, i - 1); } }

排序算法性能比较

2025年王道中数据结构的排序算法

相关推荐