数据结构

图片.png

<h1>O(n^2)的排序算法：</h1>

• 选择排序
  比较的是当前没有排序中的元素最小的元素移动到最前面。

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
template<typename T>
void SelectSort(T arr[],int n){
  for(int i=0;i<n-1;i++){
    int minIndex=i;
    for(int j=i+1;j<n;j++){
        if(arr[minIndex]>arr[j]){

            minIndex=j;
        }
    }
     swap(arr[minIndex],arr[i]);
  }

}
int main(){
  int a[5]={2,4,1,7,9};
  SelectSort(a,5);
  for(int i=0;i<5;i++){
    cout<<a[i]<<" ";

  }
  cout<<endl;
  float b[4]={2.3,1.5,2.8,1.1};
  SelectSort(b,4);
  for(int i=0;i<4;i++){
    cout<<b[i]<<" ";

  }
  cout<<endl;
  string c[4]={"D","C","B","A"};
  SelectSort(c,4);
  for(int i=0;i<4;i++){
    cout<<c[i]<<" ";

  }
  return 0;
}

测试中的辅助函数：

#ifndef INC_03_SELECTION_SORT_DETECT_PERFORMANCE_SORTTESTHELPER_H
#define INC_03_SELECTION_SORT_DETECT_PERFORMANCE_SORTTESTHELPER_H

#include <iostream>
#include <ctime>
#include <cassert>
#include <string>

using namespace std;


namespace SortTestHelper {

    // 生成有n个元素的随机数组,每个元素的随机范围为[rangeL, rangeR]
    int *generateRandomArray(int n, int rangeL, int range R) {

        assert(rangeL <= rangeR);

        int *arr = new int[n];

        srand(time(NULL));
        for (int i = 0; i < n; i++)
            arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;
        return arr;
    }

    template<typename T>
    void printArray(T arr[], int n) {

        for (int i = 0; i < n; i++)
            cout << arr[i] << " ";
        cout << endl;

        return;
    }

    template<typename T>
    bool isSorted(T arr[], int n) {

        for (int i = 0; i < n - 1; i++)
            if (arr[i] > arr[i + 1])
                return false;

        return true;
    }

    template<typename T>
    void testSort(const string &sortName, void (*sort)(T[], int), T arr[], int n) {

        clock_t startTime = clock();
        sort(arr, n);
        clock_t endTime = clock();

        assert(isSorted(arr, n));
        cout << sortName << " : " << double(endTime - startTime) / CLOCKS_PER_SEC << " s" << endl;

        return;
    }

};

• 插入排序

#include <iostream>
#include <algorithm>
using namespace std;
template<typename T>
void insertSort(T arr[],int n){
   for(int i=1;i<n;i++){
    //寻找元素arr[i]合适的插入位置
     for(int j=i;j>0;j--){
        if(arr[j]<arr[j-1]){
            swap(arr[j],arr[j-1]);
        }else{
        break;
        }
     }
   }
}
int main(){
   int a[5]={3,1,6,2,7};
   insertSort(a,5);
   for(int i=0;i<5;i++){
    cout<<a[i]<<" ";
    }
   return 0;
}

正常来说插入排序是要比选择排序时间要短的，<b>因为在第二层循环是可以提前终止的。</b>但是实际运行的时候，插入排序的性能是差的。是因为插入排序在第二层内层循环的时候是不断的swap交换的更耗时，所以性能不好。下面进行改进：
把一次又一次的交换操作（一次交换是三次赋值），换成一次赋值，
改进后的插入排序：

#include <iostream>
#include <algorithm>
using namespace std;
template<typename T>
void insertSort(T arr[],int n){
   for(int i=1;i<n;i++){
    //寻找元素arr[i]合适的插入位置
     T e=arr[i];
     int j;//j保存元素e应该插入的位置
     for(j=i;j>0&&arr[j-1]>e;j--){

            arr[j]=arr[j-1];
        }
        arr[j]=e;
     }
   }
int main(){
   int a[5]={3,1,6,2,7};
   insertSort(a,5);
   for(int i=0;i<5;i++){
    cout<<a[i]<<" ";
    }
   return 0;
}

对于一个近乎有序的数组来说，插入排序的性能将远远高于选择排序，甚至要快于nlog(n)的性能。这个特性是非常重要的，在实际工作中相当常见（比如有几个错误的日志排序中）。这个时候插入排序是一个近乎于O(N)的算法。正因为这个特性插入排序回作为其他排序过程的一个子过程进行演化。
那么相对于几乎完全有序的数组来说，另一种比较高效的排序算法就是冒泡排序。

• 冒泡排序

#include <iostream>
#include <algorithm>
using namespace std;
void bubble(int a[],int n){
int flag=1;
 for(int i=0;i<n&&flag;i++){
   flag=0;
   for(int j=n-1;j>=i;j--){
    if(a[j]>a[j+1]){
        swap(a[j],a[j+1]);
        flag=1;
    }
    }
 }
}
int main(){
 int arr[6]={3,1,7,6,2,9};
 bubble(arr,6);
 for(int i=0;i<6;i++){
    cout<<arr[i]<<" ";
 }
 return 0;
}

从插入排序可以延伸出另一种排序--<b>希尔排序</b>，它的时间复杂度在nlogn和n^2之间。

• 希尔排序：

时间复杂度分析：

• O(nlogn)的算法