几个排序算法记录

r囧r小猫 2022-04-24 09:50 177阅读 0赞

直接插入排序：插入

将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。

时间复杂度：O（n^2）

void print(int a[], int n ,int i){
    
    	cout<<i <<":";
    
    	for(int j= 0; j<8; j++){
    
    		cout<<a[j] <<" ";
    
    	}
    
    	cout<<endl;
    
    }
    
     
    
     
    
    void InsertSort(int a[], int n)
    
    {
    
    	for(int i= 1; i<n; i++){
    
    		if(a[i] < a[i-1]){               //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入
    
    			int j= i-1;	
    
    			int x = a[i];		 //复制为哨兵，即存储待排序元素
    
    			a[i] = a[i-1];           //先后移一个元素
    
    			while(x < a[j]){	 //查找在有序表的插入位置
    
    				a[j+1] = a[j];
    
    				j--;		 //元素后移
    
    			}
    
    			a[j+1] = x;		 //插入到正确位置
    
    		}
    
    		print(a,n,i);			//打印每趟排序的结果
    
    	}
    
    	
    
    }
    
     
    
    int main(){
    
    	int a[8] = {3,1,5,7,2,4,9,6};
    
    	InsertSort(a,8);
    
    	print(a,8,8);
    
    }

Java：

/**
     * 插入排序
     *
     * 1. 从第一个元素开始，该元素可以认为已经被排序
     * 2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
     * 3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
     * 4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
     * 5. 将新元素插入到该位置后
     * 6. 重复步骤2~5
     * @param arr  待排序数组
     */
    public static void insertionSort(int[] arr){
        for( int i = 1; i < arr.length; i++ ) {
            int temp = arr[i];    // 取出下一个元素，在已经排序的元素序列中从后向前扫描
            for( int j = i; j >= 0; j-- ) {
                if( j > 0 && arr[j-1] > temp ) {
                    arr[j] = arr[j-1];    // 如果该元素（已排序）大于取出的元素temp，将该元素移到下一位置
                    System.out.println("Temping:  " + Arrays.toString(arr));
                } else {
                    // 将新元素插入到该位置后
                    arr[j] = temp;
                    System.out.println("Sorting:  " + Arrays.toString(arr));
                    break;
                }
            }
        }
    }
    
    // 交换次数较多的实现
    public static void insertionSort(int[] arr){
        for( int i=0; i<arr.length-1; i++ ) {
            for( int j=i+1; j>0; j-- ) {
                if( arr[j-1] <= arr[j] )
                    break;
                int temp = arr[j];      //交换操作
                arr[j] = arr[j-1];
                arr[j-1] = temp;
                System.out.println("Sorting:  " + Arrays.toString(arr));
            }
        }
    }

希尔排序：插入

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。  
操作方法：  
选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1； 按增量序列个数k，对序列进行k 趟排序； 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

时间复杂度：O(n1+§)),§介于0和1之间

void print(int a[], int n ,int i){
    
    	cout<<i <<":";
    
    	for(int j= 0; j<8; j++){
    
    		cout<<a[j] <<" ";
    
    	}
    
    	cout<<endl;
    
    }
    
    /**
    
     * 直接插入排序的一般形式
    
     *
    
     * @param int dk 缩小增量，如果是直接插入排序，dk=1
    
     *
    
     */
    
     
    
    void ShellInsertSort(int a[], int n, int dk)
    
    {
    
    	for(int i= dk; i<n; ++i){
    
    		if(a[i] < a[i-dk]){			//若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入
    
    			int j = i-dk;	
    
    			int x = a[i];			//复制为哨兵，即存储待排序元素
    
    			a[i] = a[i-dk];			//首先后移一个元素
    
    			while(x < a[j]){		//查找在有序表的插入位置
    
    				a[j+dk] = a[j];
    
    				j -= dk;			 //元素后移
    
    			}
    
    			a[j+dk] = x;			//插入到正确位置
    
    		}
    
    		print(a, n,i );
    
    	}
    
    	
    
    }
    
     
    
    /**
    
     * 先按增量d（n/2,n为要排序数的个数进行希尔排序
    
     *
    
     */
    
    void shellSort(int a[], int n){
    
     
    
    	int dk = n/2;
    
    	while( dk >= 1  ){
    
    		ShellInsertSort(a, n, dk);
    
    		dk = dk/2;
    
    	}
    
    }
    
    int main(){
    
    	int a[8] = {3,1,5,7,2,4,9,6};
    
    	//ShellInsertSort(a,8,1); //直接插入排序
    
    	shellSort(a,8);			  //希尔插入排序
    
    	print(a,8,8);
    
    }

java:

/**
     * 希尔排序
     *
     * 1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；（一般初次取数组半长，之后每次再减半，直到增量为1）
     * 2. 按增量序列个数k，对序列进行k 趟排序；
     * 3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。
     *    仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
     * @param arr  待排序数组
     */
    public static void shellSort(int[] arr){
        int gap = arr.length / 2;
        for (; gap > 0; gap /= 2) {      //不断缩小gap，直到1为止
            for (int j = 0; (j+gap) < arr.length; j++){     //使用当前gap进行组内插入排序
                for(int k = 0; (k+gap)< arr.length; k += gap){
                    if(arr[k] > arr[k+gap]) {
                        int temp = arr[k+gap];      //交换操作
                        arr[k+gap] = arr[k];
                        arr[k] = temp;
                        System.out.println("    Sorting:  " + Arrays.toString(arr));
                    }
                }
            }
        }
    }

冒泡排序：交换

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

时间复杂度：(O(n^2))

void bubbleSort(int a[], int n){
    
    	for(int i =0 ; i< n-1; ++i) {
    
    		for(int j = 0; j < n-i-1; ++j) {
    
    			if(a[j] > a[j+1])
    
    			{
    
    				int tmp = a[j] ; a[j] = a[j+1] ;  a[j+1] = tmp;
    
    			}
    
    		}
    
    	}
    
    }

改进：

void Bubble_2 ( int r[], int n){
    
    	int low = 0; 
    
    	int high= n -1; //设置变量的初始值
    
    	int tmp,j;
    
    	while (low < high) {
    
    		for (j= low; j< high; ++j) //正向冒泡,找到最大者
    
    			if (r[j]> r[j+1]) {
    
    				tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;
    
    			} 
    
    		--high;					//修改high值, 前移一位
    
    		for ( j=high; j>low; --j) //反向冒泡,找到最小者
    
    			if (r[j]<r[j-1]) {
    
    				tmp = r[j]; r[j]=r[j-1];r[j-1]=tmp;
    
    			}
    
    		++low;					//修改low值,后移一位
    
    	} 
    
    }

java:

/**
     * 冒泡排序
     *
     * ①. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
     * ②. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
     * ③. 针对所有的元素重复以上的步骤，除了最后一个。
     * ④. 持续每次对越来越少的元素重复上面的步骤①~③，直到没有任何一对数字需要比较。
     * @param arr  待排序数组
     */
    public static void bubbleSort(int[] arr){
        for (int i = arr.length - 1; i > 0; i--) {      //外层循环移动游标
            for(int j = 0; j < i; j++){    //内层循环遍历游标及之后(或之前)的元素
                if(arr[j] > arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    System.out.println("Sorting: " + Arrays.toString(arr));
                }
            }
        }
    }

快速排序：交换

1）选择一个基准元素,通常选择第一个元素或者最后一个元素,  
2）通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。  
3）此时基准元素在其排好序后的正确位置  
4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

时间复杂度：(O(nlog2n)

void print(int a[], int n){
    
    	for(int j= 0; j<n; j++){
    
    		cout<<a[j] <<"  ";
    
    	}
    
    	cout<<endl;
    
    }
    
     
    
    void swap(int *a, int *b)
    
    {
    
    	int tmp = *a;
    
    	*a = *b;
    
    	*b = tmp;
    
    }
    
     
    
    int partition(int a[], int low, int high)
    
    {
    
    	int privotKey = a[low];					//基准元素
    
    	while(low < high){					//从表的两端交替地向中间扫描
    
    		while(low < high  && a[high] >= privotKey) --high; //从high 所指位置向前搜索，至多到low+1 位置。将比基准元素小的交换到低端
    
    		swap(&a[low], &a[high]);
    
    		while(low < high  && a[low] <= privotKey ) ++low;
    
    		swap(&a[low], &a[high]);
    
    	}
    
    	print(a,10);
    
    	return low;
    
    }
    
     
    
     
    
    void qsort_improve(int r[ ],int low,int high, int k){
    
    	if( high -low > k ) { //长度大于k时递归, k为指定的数
    
    		int pivot = partition(r, low, high); // 调用的Partition算法保持不变
    
    		qsort_improve(r, low, pivot - 1,k);
    
    		qsort_improve(r, pivot + 1, high,k);
    
    	} 
    
    } 
    
    void quickSort(int r[], int n, int k){
    
    	qsort_improve(r,0,n,k);//先调用改进算法Qsort使之基本有序
    
     
    
    	//再用插入排序对基本有序序列排序
    
    	for(int i=1; i<=n;i ++){
    
    		int tmp = r[i]; 
    
    		int j=i-1;
    
    		while(tmp < r[j]){
    
    			r[j+1]=r[j]; j=j-1; 
    
    		}
    
    		r[j+1] = tmp;
    
    	} 
    
     
    
    } 
    
     
    
     
    
     
    
    int main(){
    
    	int a[10] = {3,1,5,7,2,4,9,6,10,8};
    
    	cout<<"初始值：";
    
    	print(a,10);
    
    	quickSort(a,9,4);
    
    	cout<<"结果：";
    
    	print(a,10);
    
     
    
    }

java:

/**
     * 快速排序（递归）
     *
     * ①. 从数列中挑出一个元素，称为"基准"（pivot）。
     * ②. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
     * ③. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
     * @param arr   待排序数组
     * @param low   左边界
     * @param high  右边界
     */
    public static void quickSort(int[] arr, int low, int high){
        if(arr.length <= 0) return;
        if(low >= high) return;
        int left = low;
        int right = high;
    
        int temp = arr[left];   //挖坑1：保存基准的值
        while (left < right){
            while(left < right && arr[right] >= temp){  //坑2：从后向前找到比基准小的元素，插入到基准位置坑1中
                right--;
            }
            arr[left] = arr[right];
            while(left < right && arr[left] <= temp){   //坑3：从前往后找到比基准大的元素，放到刚才挖的坑2中
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = temp;   //基准值填补到坑3中，准备分治递归快排
        System.out.println("Sorting: " + Arrays.toString(arr));
        quickSort(arr, low, left-1);
        quickSort(arr, left+1, high);
    }

归并排序：

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

时间复杂度：(O(nlog2n)

void MSort(ElemType *r, ElemType *rf,int s, int t)
    
    { 
    
    	ElemType *rf2;
    
    	if(s==t) r[s] = rf[s];
    
    	else
    
    	{ 
    
    		int m=(s+t)/2;			/*平分*p 表*/
    
    		MSort(r, rf2, s, m);		/*递归地将p[s…m]归并为有序的p2[s…m]*/
    
    		MSort(r, rf2, m+1, t);		/*递归地将p[m+1…t]归并为有序的p2[m+1…t]*/
    
    		Merge(rf2, rf, s, m+1,t);	/*将p2[s…m]和p2[m+1…t]归并到p1[s…t]*/
    
    	}
    
    }
    
    void MergeSort_recursive(ElemType *r, ElemType *rf, int n)
    
    {   /*对顺序表*p 作归并排序*/
    
    	MSort(r, rf,0, n-1);
    
    }

java:

/**
     * 归并排序（递归）
     *
     * ①. 将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列，排序后每个序列包含两个元素；
     * ②. 将上述序列再次归并，形成 floor(n/4)个序列，每个序列包含四个元素；
     * ③. 重复步骤②，直到所有元素排序完毕。
     * @param arr    待排序数组
     */
    public static int[] mergingSort(int[] arr){
        if(arr.length <= 1) return arr;
    
        int num = arr.length >> 1;
        int[] leftArr = Arrays.copyOfRange(arr, 0, num);
        int[] rightArr = Arrays.copyOfRange(arr, num, arr.length);
        System.out.println("split two array: " + Arrays.toString(leftArr) + " And " + Arrays.toString(rightArr));
        return mergeTwoArray(mergingSort(leftArr), mergingSort(rightArr));      //不断拆分为最小单元，再排序合并
    }
    
    private static int[] mergeTwoArray(int[] arr1, int[] arr2){
        int i = 0, j = 0, k = 0;
        int[] result = new int[arr1.length + arr2.length];  //申请额外的空间存储合并之后的数组
        while(i < arr1.length && j < arr2.length){      //选取两个序列中的较小值放入新数组
            if(arr1[i] <= arr2[j]){
                result[k++] = arr1[i++];
            }else{
                result[k++] = arr2[j++];
            }
        }
        while(i < arr1.length){     //序列1中多余的元素移入新数组
            result[k++] = arr1[i++];
        }
        while(j < arr2.length){     //序列2中多余的元素移入新数组
            result[k++] = arr2[j++];
        }
        System.out.println("Merging: " + Arrays.toString(result));
        return result;
    }

堆排序：选择

堆排序是一种树形选择排序，是对直接选择排序的有效改进。基本思想：  
堆的定义如下：具有n个元素的序列（k1,k2,...,kn),当且仅当满足  
时称之为堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最小项（小顶堆）。  
若以一维数组存储一个堆，则堆对应一棵完全二叉树，且所有非叶结点的值均不大于(或不小于)其子女的值，根结点（堆顶元素）的值是最小(或最大)的。

时间复杂度：(O(nlog2n)

void print(int a[], int n){
    
    	for(int j= 0; j<n; j++){
    
    		cout<<a[j] <<"  ";
    
    	}
    
    	cout<<endl;
    
    }
    
     
    
     
    
     
    
    /**
    
     * 已知H[s…m]除了H[s] 外均满足堆的定义
    
     * 调整H[s],使其成为大顶堆.即将对第s个结点为根的子树筛选, 
    
     *
    
     * @param H是待调整的堆数组
    
     * @param s是待调整的数组元素的位置
    
     * @param length是数组的长度
    
     *
    
     */
    
    void HeapAdjust(int H[],int s, int length)
    
    {
    
    	int tmp  = H[s];
    
    	int child = 2*s+1; //左孩子结点的位置。(i+1 为当前调整结点的右孩子结点的位置)
    
        while (child < length) {
    
    		if(child+1 <length && H[child]<H[child+1]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)
    
    			++child ;
    
    		}
    
    		if(H[s]<H[child]) {  // 如果较大的子结点大于父结点
    
    			H[s] = H[child]; // 那么把较大的子结点往上移动，替换它的父结点
    
    			s = child;		 // 重新设置s ,即待调整的下一个结点的位置
    
    			child = 2*s+1;
    
    		}  else {			 // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出
    
    			 break;
    
    		}
    
    		H[s] = tmp;			// 当前待调整的结点放到比其大的孩子结点位置上
    
    	}
    
    	print(H,length);
    
    }
    
     
    
     
    
    /**
    
     * 初始堆进行调整
    
     * 将H[0..length-1]建成堆
    
     * 调整完之后第一个元素是序列的最小的元素
    
     */
    
    void BuildingHeap(int H[], int length)
    
    { 
    
    	//最后一个有孩子的节点的位置 i=  (length -1) / 2
    
    	for (int i = (length -1) / 2 ; i >= 0; --i)
    
    		HeapAdjust(H,i,length);
    
    }
    
    /**
    
     * 堆排序算法
    
     */
    
    void HeapSort(int H[],int length)
    
    {
    
        //初始堆
    
    	BuildingHeap(H, length);
    
    	//从最后一个元素开始对序列进行调整
    
    	for (int i = length - 1; i > 0; --i)
    
    	{
    
    		//交换堆顶元素H[0]和堆中最后一个元素
    
    		int temp = H[i]; H[i] = H[0]; H[0] = temp;
    
    		//每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整
    
    		HeapAdjust(H,0,i);
    
      }
    
    } 
    
     
    
    int main(){
    
    	int H[10] = {3,1,5,7,2,4,9,6,10,8};
    
    	cout<<"初始值：";
    
    	print(H,10);
    
    	HeapSort(H,10);
    
    	//selectSort(a, 8);
    
    	cout<<"结果：";
    
    	print(H,10);
    
     
    
    }

java:

/**
     * 堆排序
     *
     * 1. 先将初始序列K[1..n]建成一个大顶堆, 那么此时第一个元素K1最大, 此堆为初始的无序区.
     * 2. 再将关键字最大的记录K1 (即堆顶, 第一个元素)和无序区的最后一个记录 Kn 交换, 由此得到新的无序区K[1..n−1]和有序区K[n], 且满足K[1..n−1].keys⩽K[n].key
     * 3. 交换K1 和 Kn 后, 堆顶可能违反堆性质, 因此需将K[1..n−1]调整为堆. 然后重复步骤②, 直到无序区只有一个元素时停止.
     * @param arr  待排序数组
     */
    public static void heapSort(int[] arr){
        for(int i = arr.length; i > 0; i--){
            max_heapify(arr, i);
    
            int temp = arr[0];      //堆顶元素(第一个元素)与Kn交换
            arr[0] = arr[i-1];
            arr[i-1] = temp;
        }
    }
    
    private static void max_heapify(int[] arr, int limit){
        if(arr.length <= 0 || arr.length < limit) return;
        int parentIdx = limit / 2;
    
        for(; parentIdx >= 0; parentIdx--){
            if(parentIdx * 2 >= limit){
                continue;
            }
            int left = parentIdx * 2;       //左子节点位置
            int right = (left + 1) >= limit ? left : (left + 1);    //右子节点位置，如果没有右节点，默认为左节点位置
    
            int maxChildId = arr[left] >= arr[right] ? left : right;
            if(arr[maxChildId] > arr[parentIdx]){   //交换父节点与左右子节点中的最大值
                int temp = arr[parentIdx];
                arr[parentIdx] = arr[maxChildId];
                arr[maxChildId] = temp;
            }
        }
        System.out.println("Max_Heapify: " + Arrays.toString(arr));
    }

简单选择排序:选择

在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

时间复杂度：O(n^2)

void print(int a[], int n ,int i){
    
    	cout<<"第"<<i+1 <<"趟 : ";
    
    	for(int j= 0; j<8; j++){
    
    		cout<<a[j] <<"  ";
    
    	}
    
    	cout<<endl;
    
    }
    
    /**
    
     * 数组的最小值
    
     *
    
     * @return int 数组的键值
    
     */
    
    int SelectMinKey(int a[], int n, int i)
    
    {
    
    	int k = i;
    
    	for(int j=i+1 ;j< n; ++j) {
    
    		if(a[k] > a[j]) k = j;
    
    	}
    
    	return k;
    
    }
    
     
    
    /**
    
     * 选择排序
    
     *
    
     */
    
    void selectSort(int a[], int n){
    
    	int key, tmp;
    
    	for(int i = 0; i< n; ++i) {
    
    		key = SelectMinKey(a, n,i);           //选择最小的元素
    
    		if(key != i){
    
    			tmp = a[i];  a[i] = a[key]; a[key] = tmp; //最小元素与第i位置元素互换
    
    		}
    
    		print(a,  n , i);
    
    	}
    
    }
    
    int main(){
    
    	int a[8] = {3,1,5,7,2,4,9,6};
    
    	cout<<"初始值：";
    
    	for(int j= 0; j<8; j++){
    
    		cout<<a[j] <<"  ";
    
    	}
    
    	cout<<endl<<endl;
    
    	selectSort(a, 8);
    
    	print(a,8,8);
    
    }

改进：

void SelectSort(int r[],int n) {
    
    	int i ,j , min ,max, tmp;
    
    	for (i=1 ;i <= n/2;i++) {  
    
    		// 做不超过n/2趟选择排序 
    
    		min = i; max = i ; //分别记录最大和最小关键字记录位置
    
    		for (j= i+1; j<= n-i; j++) {
    
    			if (r[j] > r[max]) { 
    
    				max = j ; continue ; 
    
    			}  
    
    			if (r[j]< r[min]) { 
    
    				min = j ; 
    
    			}   
    
    	  }  
    
    	  //该交换操作还可分情况讨论以提高效率
    
    	  tmp = r[i-1]; r[i-1] = r[min]; r[min] = tmp;
    
    	  tmp = r[n-i]; r[n-i] = r[max]; r[max] = tmp; 
    
     
    
    	} 
    
    }

java:

/**
     * 选择排序
     *
     * 1. 从待排序序列中，找到关键字最小的元素；
     * 2. 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
     * 3. 从余下的 N - 1 个元素中，找出关键字最小的元素，重复①、②步，直到排序结束。
     *    仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
     * @param arr  待排序数组
     */
    public static void selectionSort(int[] arr){
        for(int i = 0; i < arr.length-1; i++){
            int min = i;
            for(int j = i+1; j < arr.length; j++){    //选出之后待排序中值最小的位置
                if(arr[j] < arr[min]){
                    min = j;
                }
            }
            if(min != i){
                int temp = arr[min];      //交换操作
                arr[min] = arr[i];
                arr[i] = temp;
                System.out.println("Sorting:  " + Arrays.toString(arr));
            }
        }
    }

![排序算法总结][20150215133440876]

[20150215133440876]: /images/20220216/f9333db33cf74aaba65ca4aa01dac227.png