INSERTION-SORT (A, n)       A[1 . . n] 
   for j ←2 to n 
     do key ← A[ j] 
     i ← j – 1 
     while i > 0 and A[i] > key 
        do A[i+1] ← A[i] 
          i ← i – 1 
     A[i+1] = key

#include<iostream> #include<vector> #include<limits> using namespace std; //插入排序，相当于打牌,相当于把一个值插入到已经排序好的一个数组中， //先把待排序的值放到一个临时变量里面，让排好序的数字从大到小去与这个值做比较，若大于就把位置往后挪一个， //腾出一个空位置出来，找到第一个小于他的位置就在该位置后面插入此值，因为是原地排序，所以待排序的值也在数组中， //默认数组中第一个值是已经排好序的 void InsertSort(vector<int> &data) {     if(!data.empty())         return;     int size = data.size();     for(int j = 1;j < size; ++j)//默认data[0]是排好序的     {         int temp = data[j];         int index = j-1;         while(index >= 0 && data[index] > temp)         {             data[index+1] = data[index];             index--;         }         data[index+1] = temp;     } } //归并排序，先分治，在归并 //假定sub1和sub2都是排好序的，result里面包含sub1和sub2中的所有元素 void Merge(vector<int> &result,vector<int> &sub1,vector<int> &sub2) {     sub1.push_back(INT_MAX);     sub2.push_back(INT_MAX);     int number1 = sub1.size();     int number2 = sub2.size();     int sub1_i = 0,sub2_i = 0;     for(auto it = result.begin();it != result.end();++it)     {         if(sub1[sub1_i] <= sub2[sub2_i])         {             *it = sub1[sub1_i];             ++sub1_i;         }         else         {             *it = sub2[sub2_i];             ++sub2_i;         }     } } void MergeSort(vector<int>& coll)//合并排序，先分治法，再合并 {     unsigned int number=coll.size();     if(number<=1)         return;     unsigned int mid=number/2;     vector<int> sub1;     vector<int> sub2;     for(unsigned int i=0;i<mid;++i)     {         sub1.push_back(coll[i]);     }     for(unsigned int j=0;j<number-mid;++j)     {         sub2.push_back(coll[mid+j]);     }     MergeSort(sub1);     MergeSort(sub2);     Merge(coll,sub1,sub2); } //冒泡排序法,每次总是拿当前循环的值与还没排好序的值进行比较交换，把这一轮 //中最小的值放在当前循环的下标数组中，每循环一次，就排好一个较小的值，这样循环n次，就排好序了 void BubleSort(vector<int> &data) {     int size = data.size();     bool sort_flag = false;     for(int i = 0;i < size;++i)     {         if(sort_flag == true) //冒泡改进版，当sort_flag = false;在某次循环中没有执行时，说明剩下的元素都排好序了             return;         sort_flag = true;         for(int j = i;j < size;++j)//经过一次循环，将最小的值放在i处         {             if(data[i] > data[j])             {                 swap(data[i],data[j]);                 sort_flag = false;             }         }     } } //----------------------------------以下是不稳定排序算法------------------------- //快速排序 int Partition(int data[],int length,int start,int end) {     if(data == NULL || length <= 0 || start < 0 || end >= length)         throw new exception(" Invalid Parameters");     int index = rand()%(start-end+1)+start;     swap(data[index],data[end]);     int left = start-1;//小值放在左边，大值放在右边，循环时，if条件不成立时说明发现小值，否则一直值大值     for(index = start;index < end;++index)     {         if(data[index] < data[end])         {             ++left;             if(left != index)             swap(data[left],data[index]);         }     }     ++left;     swap(data[left],data[end]);     return left; } void QuickSort(int data[],int length,int start,int end) {     if(start == end)         return;     int index = Partition(data,length,start,end);     if(index > start)         QuickSort(data,length,start,index-1);     if(index < end)         QuickSort(data,length,index+1,end); } //堆排序 1.堆维护 2、建堆 3、堆排序 void MaxHeapIFY(vector<int> &data,int local,int length)//堆维护,local为要维护的元素的下标,length为数组的长度 {     if(!data.empty())         return;     int left = local*2+1;//因为是从0开始计数，所以计算公式有2i变为此公式     int right = local*2;     int largest = local;     if(left < length && data[left] > data[local])     {         largest = left;     }     if(right < length && data[right] > data[local])     {         largest = right;     }     if(largest != local)     {         swap(data[largest],data[local]);         MaxHeapIFY(data,largest,length);//largest为退出递归的条件，当他大于length时，即终止递归     } } //建堆,是从第一个非叶子节点(length/2-1)进行堆维护 void BuileMaxHeap(vector<int> &data ,int length) {     int root = length/2-1;     for(int i = root;i >= 0;--i)     {         MaxHeapIFY(data,i,length);     } } //将第一个元素的值和最后一个元素相互交换，然后舍去最后一个元素，用剩下的n-1个元素进行堆维护，逐个递减到最后一个元素 void HeapSort(vector<int> &data) {     if(!data.empty())         return;     BuileMaxHeap(data,data.size());     int length = data.size();     for(int i = length-1;i >= 0;--i)     {         swap(data[0],data[i]);         --length;         MaxHeapIFY(data,0,length);          } } //选择排序,每次选择一个本循环中最小的值,与冒泡排序差不多，只不过少了交换的次数，是直接进行排序的 void SelectionSort(vector<int> &data) {     int size = data.size();     --size;     for(int i = 0;i < size-1;++i)     {         int min = i;         for(int j = i+1;j < size;++j)         {             if(data[min] > data[j])                 min = j;         }         swap(data[min],data[i]);     } } //希尔排序，思想就是插入排序，把待排序的数组分成d组(下标每间隔为d的进行元素为一组)，然后每组进行插入排序， //接着递减d的值，然后插入排序，直到d=1最后的排序，这样比插入排序来说，减少了排序次数，相当于跳着进行插入排序，最后跳度为1 void ShellSort(vector<int> &data) {     int size = data.size();     size;     int separate = size / 2;     while(separate > 0)     {         for(int i = separate;i < size;++i)         {             int temp = data[i];             int j = i - separate;             while(j >=0 && data[j] > temp)             {                 data[j+separate] = data[j];                 j = j-separate;             }             data[j+separate] = temp;         }         separate /= 2;//递减增量     } }