比较常见的几种排序算法

原理：
通过相邻元素的比较和交换，每一轮将最大的元素“冒泡”到数组末尾。

时间复杂度：

• 最好：O(n)（已有序时优化后）

• 平均/最坏：O(n²)

稳定性：稳定（相等元素不交换）

优点：简单易懂，无需额外空间。

缺点：效率低，不适用于大规模数据。

适用场景：教学示例或小规模数据。

1. 冒泡排序 (稳定，时间复杂度 O(n²))

c



void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {  // 遍历次数
        int swapped = 0;  // 优化：若本轮未交换则提前结束
        for (int j = 0; j < n-i-1; j++) {  // 每次比较相邻元素
            if (arr[j] > arr[j+1]) {  
                // 交换元素
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                swapped = 1;
            }
        }
        if (!swapped) break;  // 无交换则已有序
    }
}

2. 选择排序 (Selection Sort)

原理：
每一轮从未排序部分选出最小值，与当前未排序部分的第一个元素交换。

时间复杂度：

• 所有情况：O(n²)

稳定性：不稳定（交换可能破坏相等元素的顺序）

优点：简单，原地排序。

缺点：效率低，无论数据是否有序都需要完整遍历。

适用场景：小规模数据或对内存敏感的场景。

c

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int min_idx = i;  // 记录最小元素下标
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        // 将最小值交换到当前位置
        int temp = arr[i];
        arr[i] = arr[min_idx];
        arr[min_idx] = temp;
    }
}

3. 插入排序 (Insertion Sort)

原理：
将数组分为已排序和未排序两部分，逐个将未排序元素插入到已排序部分的正确位置。

时间复杂度：

• 最好：O(n)（已有序时）

• 平均/最坏：O(n²)

稳定性：稳定（插入时保持相等元素的相对顺序）

优点：对小规模或部分有序数据高效。

缺点：大规模乱序数据效率低。

适用场景：小规模数据、数据基本有序或在线排序（数据逐步到达）。

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {  // 从第二个元素开始
        int key = arr[i];  // 当前待插入元素
        int j = i - 1;
        // 将比key大的元素后移
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;  // 插入正确位置
    }
}

4. 快速排序 (Quick Sort)

原理：
采用分治法，选择一个基准元素（pivot），将数组分为小于基准和大于基准的两部分，递归排序子数组。

时间复杂度：

• 平均/最好：O(n log n)

• 最坏：O(n²)（如数组已有序且选固定基准）

稳定性：不稳定（分区交换可能破坏顺序）

优点：实际应用中速度最快（平均性能好）。

缺点：最坏情况效率低，递归栈可能溢出。

优化手段：随机选基准、三数取中法。

适用场景：大规模数据，对稳定性无要求。

// 分区函数
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选最后一个元素为基准
    int i = low - 1;  // 记录较小元素的边界
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            // 交换较小元素到左侧
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // 将基准放到正确位置
    int temp = arr[i+1];
    arr[i+1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);  // 获取基准位置
        quickSort(arr, low, pi-1);  // 递归左半区
        quickSort(arr, pi+1, high); // 递归右半区
    }
}

// 调用示例：quickSort(arr, 0, n-1);

5. 归并排序 (Merge Sort)

原理：
采用分治法，将数组递归分成两半，分别排序后合并两个有序子数组。

时间复杂度：

• 所有情况：O(n log n)

稳定性：稳定（合并时保留相等元素的顺序）

优点：稳定且时间复杂度稳定。

缺点：需要额外存储空间（O(n)）。

适用场景：需要稳定排序、数据规模较大且内存允许。

// 合并两个有序子数组
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];  // 临时数组

    // 复制数据到临时数组
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];

    // 合并过程
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // 处理剩余元素
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;  // 防止溢出
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

// 调用示例：mergeSort(arr, 0, n-1);

6. 希尔排序 (Shell Sort)

原理：
插入排序的改进版，通过定义递减的间隔序列（如n/2, n/4, ... 1），对间隔分组内的元素进行插入排序。

时间复杂度：

• 取决于间隔序列，一般为O(n^(1.3~2))

稳定性：不稳定（分组可能破坏相等元素的顺序）

void shellSort(int arr[], int n) {
    // 初始间隔设为n/2，逐步缩小
    for (int gap = n/2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i];  // 当前待插入元素
            int j;
            // 对间隔gap的元素进行插入排序
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

二去重复化算法：主要通过将存储单元中的数据元素通过循环遍历的方式进行删除相同数据元素，返回新定不相同的元素到新的存储空间中

1对于同一数组或者指针：

#include <stdio.h>
#define N 80
int fun(int a[], int n)
{   
  int i,j=1; //设置初始组数下标
 for(i=1;i<n;i++) //遍历数组元素
 {
    if(a[i]!=a[j-1]) //判断相邻元素是否一致
    a[j++]=a[i];   //复制新的元素
 }
  return j; //返回数组元素个数
 
  
 
 
 
 

}

int main()
{  int  a[N]={2,2,2,3,4,4,5,6,6,6,6,7,7,8,9,9,10,10,10,10},i,n=20;void NONO ();
   printf("The original data :\n");
   for(i=0; i<n; i++)printf("%3d",a[i]);
   n=fun(a,n);
   printf("\n\nThe data after deleted :\n");
   for(i=0;i<n;i++)printf("%3d",a[i]); printf("\n\n");
   NONO();
}
void NONO ()
{/* 请在此函数内打开文件，输入测试数据，调用 fun 函数，输出数据，关闭文件。 */
  FILE *rf, *wf; int a[N], n, i, j ;
  rf = fopen("in.dat","r") ;
  wf = fopen("out.dat","w") ;
  for(i = 0 ; i < 5 ; i++) {
    fscanf(rf, "%d", &n) ;
    for(j = 0 ; j < n ; j++) fscanf(rf, "%d", &a[j]) ;
    n = fun(a, n) ;
    for(j = 0 ; j < n ; j++) fprintf(wf, "%4d", a[j]) ;
    fprintf(wf, "\n") ;
  }
  fclose(rf) ; fclose(wf) ;
}

2对于对个数组或者指针的去重复化：

#include <stdio.h>

// 去重函数
int removeDuplicates(int arr[], int n, int result[]) {
    int i, j, k = 0;
    for (i = 0; i < n; i++) {  //循环原数组
        int isDuplicate = 0;       //初始化标志位
        for (j = 0; j < i; j++) {    //标志前面的数组元素
            if (arr[i] == arr[j]) {
                isDuplicate = 1; //判断是否有相同元素的标志位
                break;
            }
        }
        if (!isDuplicate) {
            result[k++] = arr[i];  将不同值放在新数组中
        }
    }
    return k;
}

int main() {
    int arr[] = {1, 2, 3, 2, 4, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    int result[100];  // 假设结果数组足够大

    int newSize = removeDuplicates(arr, n, result);

    // 输出去重后的数组
    for (int i = 0; i < newSize; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");

    return 0;
}
}