[数据结构与算法]五种排序算法

#include <iostream>
using namespace std;
void myprint(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout <<arr[i]<<" ";
        
    }
cout << endl;
}

int findpos(int arr[], int low,int high) {
    int temp = arr[low];
    while (low < high) {
        while (low<high && arr[high]>=temp) {
            high--;
        }
        arr[low] = arr[high];
        while (low < high&& arr[low] <= temp) {
            low++;
        }
        arr[high] = arr[low];
    }
    arr[low] = temp;
    return low;

}

void quicksort(int arr[], int left,int right) {//快速排序
    int n = right;
    int m = left;
    int index;
    if (m< n) {
      index = findpos(arr, left, right);
        quicksort(arr, left, index-1);
        quicksort(arr, index + 1, n);
    }
   

}
void shell_sort(int arr[], int n) {//shell排序
    for (int r = n / 2; r >= 1; r = r / 2) {
        for (int i = 0; i < r; i++) {
            int temp = arr[i];
            int  j = i - r;
            while (j >=0 && temp < arr[j])
            {
                arr[j + r] = arr[j];
                j -= r;
            }
            arr[j + r] = temp;
        }
    }
    myprint(arr, n);

} 

void insert_sort(int arr[], int n) {//直接插入排序
    for (int i = 0; i < n; i++) {
        int temp = arr[i];
       int  j = i - 1;
        while (j>=0 && temp<arr[j])
        {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
    myprint(arr, n);
}
void xuanzesort(int arr[], int n) {//选择排序
    for (int i = 0; i < n; i++) {
        int index = i;
        for (int j = i; j < n; j++) {
            if (arr[index] > arr[j]) {
                index = j;
            }
        }
        swap(arr[i], arr[index]);
    }
    myprint(arr, n);
}
void maopaosort(int arr[], int n) {
               //冒泡排序可以进行优化 哨兵方法
    for (int i = 0; i < n - 1; i++) {
        for (int j = i; j < n; j++) {
           if (arr[i] > arr[j]) {
                swap(arr[i], arr[j]);
            }
        }
    }
    myprint(arr, n);
}

int main()
{
    int arr[] = { 5,4,2,3,1 };//我们按照从小到大排序
    int n = sizeof(arr) / sizeof(int);
 
    myprint(arr, n);
    maopaosort(arr, n);
    xuanzesort(arr, n);
    insert_sort(arr, n);
    shell_sort(arr, n);
   quicksort(arr, 0, n-1);
myprint(arr, n);
    
}