排序算法实现总结_排序算法实验总结

冒泡排序：

时间复杂度是O(n²)，空间复杂度是O(1)，稳定，排序算法与数组原始序列无关。

思路：遍历待排序列，从前往后（或从后往前）两两比较相邻元素的值，若为逆序则交换位置，直至遍历结束，称为一趟冒泡。一趟冒泡的结果是将最大元素“浮至”序列末尾，已确定位置的元素不再参与下一趟冒泡过程。重复冒泡的过程，直至序列有序。通过N-1次对剩余未排序元素中最大（小）元素的上浮来实现排序，上浮过程通过交换相邻元素实现。

步骤：1.用i遍历数组，初始j为0，即从序列第一个位置开始比较。

         2.比较a[j]和a[j+1]，若a[j] > a[j+1]，交换位置。
         3.令j加1，重复步骤2，直至遍历结束。
         4.针对所有的元素重复以上的步骤，除了最后一个。
         5.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字发生交换。

    int* bubbleSort(int* A, int n) {
        for (int i = n - 1; i >= 0; i--) {
	    for (int j = 0; j < i; j++) {
                if (A[j] > A[j + 1]){
                    int temp = A[j];
                    A[j] = A[j + 1];
                    A[j + 1] = temp;
                }
            }
        }
        return A;
    }

选择排序：

时间复杂度是O(n²)，空间复杂度是O(1)，不稳定，排序算法与数组原始序列无关

思路：从头到尾遍历序列，找到数组中最小的元素交换到第一个位置，再从剩余的元素中继续找到最小元素放在第二个位置，以此类推直至序列有序。

步骤： 1.在i+1~n的范围内找到最小元素对应的位置j。（初始i为0）
          2.交换A[i]和A[j]。
          3.令i加1，重复步骤1、2。
          4.重复上述过程直至序列有序。

int* selectionSort(int* A, int n) {
        for(int i=0;i<n;i++){
            int min = i;
            for(int j=i+1;j<n;j++){  //这个循环是算法关键，它从无序序列中挑出一个最小的元素
                if(A[min]>A[j]){
                   min = j;
                }
            }
            int temp = A[min];  //下面三句完成最小元素与无序序列第一个元素的交换
            A[min] = A[i];
            A[i] = temp;
        }
        return A;
    }

插入排序：

时间复杂度是O(n²)，空间复杂度是O(1)，稳定，排序算法与数组原始顺序有关

思路：对于每个未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。通过N-1趟排序组成。第i趟排序后保证位置0到位置i上的元素为已排序状态。第i趟排序将第i个元素插入到前i-1个有序元素中。

步骤： 1.从第一个元素开始，该元素可以认为已有序。

2.取出下一个元素，在已经排序的元素序列中从后向前扫描。

3.如果被扫描的元素（已排序）大于新元素，将该元素后移一位。

4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。

5.将新元素插入到该位置后。

6.重复步骤2~5。

class InsertionSort {
public:
    int* insertionSort(int* A, int n) {
       for (int i = 1; i < n; i++){  //数组从下标1开始处理，因为第一个元素有序，所以从第二个开始处理
            int temp=A[i];//将待插入的元素暂存与temp
            int j;
            for(j = i; j > 0 && A[j-1]>temp; j--){//循环完成了从待排元素之前的元素开始扫描，如果大于待排元素，则后移一位
               A[j]=A[j-1];
            }
            A[j]=temp;//找到插入位置，将temp中暂存的待排元素插入
        } 
        return A;
    }
};

归并排序：

时间复杂度是O(nlog₂n)，空间复杂度是O(N)，稳定，排序算法与数组原始序列无关

思路：将待排序序列看成是n个长度为1的有序序列，将相邻的有序两两归并，得到n/2个长度为2的有序序列；将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。

步骤： merge()函数是将前后相邻的两个有序表归并为一个有序表，设A[start...mid]和A[mid+1...end]存放在同一顺序表的相邻位置上，每次从对应的两个段取出一个元素进行比较，将较小者复制到辅助数组temp中，最后将temp复制到A中。

int* mergeSort(int* A, int n){
     sort(A,0,n-1); return A; 
} 
//归并排序 
void sort(int *A, int start, int end)
 { int mid = (start + end)/2; 
   if(start<end) 
     { sort(A, start, mid);// 左边排序 
       sort(A, mid+1, end);// 右边排序 
       merge(A, start, mid, end);// 左右合并 
     } 
} 
//将分治的两端按大小次序填入临时数组，最后把临时数组拷贝到原数组  start到mid为一端，mid+1到end为另一端       
void merge(int *A, int start, int mid, int end){          
       int temp[end-start+1];          
       int i = start;// 左指针          
       int j = mid+1;// 右指针          
       int t = 0;         
       while(i<=mid && j<=end) // 把较小的数先移到新数组中          
       {              
        if(A[i]<=A[j])  //从小到大排序                
             temp[t++] = A[i++];             
        else                    
             temp[t++] = A[j++];         
       }  //左端或右端只有一端可能有剩余元素        
      while(i<=mid)// 把左边剩余的数移入数组               
         temp[t++] = A[i++];          
      while(j<=end) // 把右边边剩余的数移入数组               
         temp[t++] = A[j++];          
      for (int k = 0; k < t; k++) {// 把临时数组中的数拷贝到原数组             
         A[start + k] = temp[k];          
      }   
}

快速排序:

时间复杂度是O(nlog2n)，空间复杂度是O( logN)～O(N)，不稳定，排序算法与数组原始序列无关

思路： 1.选择一个元素temp作为基准。

          2.调整元素的位置，将比基准元素小的所有元素均移动到它左侧，比基准元素大于或等于的所有元素均移动到它右侧。则temp放在了其最终位置上。

3.左右区间递归执行第二步，直至各区间只有一个数或空为止，即所有元素放在了其最终位置上.

int* quickSort(int* A, int n) {
        Sort(A,0,n-1);
        return A;
    }
    //对从left到right的元素进行从大到小的排序  
    void Sort(int* A,int left,int right){  
        if(left>=right) return;
        
        int i = left, j = right;  
        int temp= A[i];//用表的第一个记录作为划分记录  
        while(i<j){    //从表的两端交替向中间扫描 
               //下面这个循环完成了一趟排序，将数组中小于temp的元素放在右边，大于的放左边  
            while(i<j && A[j]>temp) j--;//从右往左扫描找一个小于temp的元素  
            if(i<j){  
                A[i]=A[j];//放在temp左边  
                i++;//i指针右移一位  
            }  
            while(i<j && A[i]<temp) i++;//从左往右扫描找一个大于temp的元素  
            if(i<j){  
                A[j]=A[i];//放在temp右边  
                j--;//j指针左移一位  
            }  
        }  
        A[i]=temp;//将temp指针放在最终位置  
        Sort(A,left,i-1);//递归的对temp左边的元素进行排序  
        Sort(A,i+1,right);//递归的对temp右边的元素进行排序  
    }

class QuickSort {
public:
int* quickSort(int* A, int n){  
    sort(A,0,n-1);  
    return A;  
}  
void sawp(int* a ,int first,int second){  
    int  temp = a[first];  
    a[first] = a[second];  
    a[second] = temp;  
}  
void sort(int* a,int low,int high){  //三向切分的快速排序
    if(low < high){  
        int l  = low,i=low+1,h = high;  //第一个元素是切分元素，所以指针i可以从lo+1开始 
        int temp = a[low];  
        while(i <= h){        //a[i] < temp 交换a[i]和a[l]，然后i和l都自增1，i继续扫描
            if(a[i] < temp){ //小于切分元素的放在l左边，因此指针l和指针i整体右移 
                sawp(a,l++,i++);  
            }else if(a[i] > temp){  //大于切分元素的放在h右边，因此指针h需要左移
                sawp(a,i,h--);  
            }else{   //a[i] = temp i自增1，1接着继续扫描
                i++;  
            }  
        }  
        sort(a,low,l-1); //l-h的元素已经排定，只需对l左边和h右边的元素进行递归求解 
        sort(a,h+1,high);
    }  
 }  
};

堆排序：

堆排序的思路是：将无需序列构建成一个大顶堆;将堆顶元素最大值与末尾元素交换，将最大元素"沉"到数组末端;重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整 + 交换步骤，直到整个序列有序。

最后一个非叶子节点是最有一个子节点的父节点 如果堆中一共有n个子节点，那么第n个节点的父节点为[n/2].

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] 

int* heapSort(int* A, int n) {
	//1.构建大顶堆,堆顶元素为数组最大值 
	for (int i = n / 2 - 1; i >= 0; i--){ //从第一个非叶子结点从下至上，从右至左调整结构 i=[n/2]~1
		AdujustHeap(A, n, i, n - 1);
	}
	//2.调整堆结构+交换堆顶元素与末尾元素
	for (int i = n - 1; i > 0; i--){   
		int tmp = A[0];//将堆尾和堆顶交换,换出根结点中元素，放到最终位置
		A[0] = A[i];
		A[i] = tmp;
 
		AdujustHeap(A, n, 0, i - 1);//在减少了一个元素的无序序列中，重新对堆进行调整
	}
	return A;
}
//保持堆的性质
void AdujustHeap(int *A, int n, int begin, int end) {
	int parent = begin;//parent为子树的根
	int child = 2 * parent + 1;//child是parent的左孩子
	int value = A[parent];//记录子树根的值
	while (child <= end){   //沿较小值孩子结点向下筛选
		if (child < end && A[child] < A[child + 1]){  //记录孩子值较大者，若右孩子较大，则child指向右孩子
			child++;//记录值较大的孩子的序号，child变为2*parent+2
		}
		if (value < A[child]){
			A[parent] = A[child];//将A[child]调整到双亲结点的位置上
			parent = child;//修改parent和child的值，以便继续向下调整
			child = 2 * parent + 1;
		}
		else break;//调整结束
	}
	A[parent] = value;//将调整结点的值放入最终位置
}

希尔排序：

int* shellSort(int* A, int n) {
 
        for(int shell=n/2;shell>0;shell=shell/2){  //控制增量，shell是增量的大小
            for(int i=shell;i<n;i++){  //这个循环是前面的插入排序，倒着比较
                int temp=A[i];//将待插入的元素暂存与temp
                int j;
                //循环完成了从待排元素之前的元素开始扫描，如果大于待排元素，则后移h位
                for(j=i-shell;j>=0 && temp<A[j];j-=shell){
                    A[j+shell]=A[j];
                }
                A[j+shell]=temp;//找到插入位置，将temp中暂存的待排元素插入
            }
        }
        return A;
    }

计数排序：

int* countingSort(int* A, int n) {
 
        int temp[1000]={0};
        for (int i =0;i<n;i++){
            temp[A[i]]++;
        }
        int index=0;
        for (int i=0;i<1000;i++){
            if (temp[i]!=0){
                for (int j=0;j<temp[i];j++){
                    A[index]=i;
                    index++;
                }
            }
        }
        return A;  
    }

基数排序：

int* radixSort(int* A, int n) {
 
        int d = maxbit(A, n);  
        int tmp[n];    //将临时数组
        int count[10]; //计数器，存放各个桶的数据统计个数
        int radix = 1;
      for(int i = 1; i <= d; i++) //进行d次排序,按照从低位到高位的顺序执行排序过程
      {  
        int k;//每个桶中的记录数 
        for(int j = 0; j < 10; j++) // 置空各个桶的数据统计,装桶之前要先清桶  
            count[j] = 0; //每次分配前清空计数器
        for(int j = 0; j < n; j++) // 统计各个桶将要装入的数据个数
        {  
            k = (A[j] / radix) % 10; //求余得到个位数，放到对应桶中  
            count[k]++; //对应桶中的记录数加1
        } 
          
        for(int j = 1; j < 10; j++)//计算位置，count[j]表示第j个桶的右边界索引
            count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶 
         // 将数据依次装入桶中，这里要从右向左扫描，保证排序稳定性
        for(int j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中  
        {  
            k = (A[j] / radix) % 10; // 求出关键码的第k位的数字， 例如：576的第3位是5 
            tmp[count[k] - 1] = A[j];// 放入对应的桶中，count[j]-1是第j个桶的右边界索引
            count[k]--;// 对应桶的装入数据索引减一  
        } 
          
        for(int j = 0; j < n; j++) //将临时数组的内容复制到A中  
            A[j] = tmp[j];   // 将已分配好的桶中数据再倒出来，此时已是对应当前位数有序的表
        radix = radix * 10;  
      }  
      return A;
    }
   //寻找数组中最大数的位数,作为基数排序循环次数,决定排序次数 
   int maxbit(int* A, int n)   
   {  
    int d = 1; //保存最大的位数  
    int p = 10;  
    for(int i = 0; i < n; i++)  
    {  
        while(A[i] >= p){  
            p *= 10;  
            d++;  
        }  
    }  
    return d; 
   }

int* radixSort(int* A, int n) {
        for(int i=0;i<=4;i++){//总共几位数 进行最大位数次排序,按照从低位到高位的顺序执行排序过程
            sort(A,n,i);
        }
        return A;
    }
    void sort(int *A,int n,int digit){
        queue<int> que[10];         //0-9号桶
        //装桶
        for(int i=0;i<n;++i){       
            int num=A[i]/pow(10,digit);  //得到当前位数之前的数  pow(x,y)是计算x的y次方
            que[num%10].push(A[i]);  //把A[i]分装到0-9号桶，求余得到个位数，放到对应桶中 
        }
        //倒桶
        int index=0;
        for(int i=0;i<10;i++){     
            while(!que[i].empty()){     //桶不为空
                A[index]=que[i].front();   //依次倒出桶中的数
                que[i].pop();
                index++;
            }
        }
    }