安科网

排 序

xpsallwell

xpsallwell

2011-07-31

关注 关注

1. 排序的分类

    在介绍有关排序的算法之前，先来介绍与排序相关的基本概念。本节主要介绍排序的基本概念及相关概念。排序：把一个无序的元素序列按照元素的关键字递增或递减排列为有序的序列。

  • 稳定排序和不稳定排序：在排列过程中，如果存在两个关键字相等即ki=kj(1≤i≤n,1≤j≤n,i≠j)，在排序前对应的元素Ei在Ej之前。
  • 内排序和外排序：根据排序过程中，所利用的内存储器和外存储器的情况，将排序分为两类：内部排序和外部排序。
  • 内排序的方法：按照排序过程中采用的策略将排序分为几个大类：插入排序、选择排序、交换排序和归并排序。这些排序方法各有优点和不足，在使用时，可根据具体情况选择比较合适的方法。

    排序分类如下所示：

（1）插入排序（直接插入排序、折半插入排序、希尔排序）；

（2）交换排序（冒泡泡排序、快速排序）；

（3）选择排序（直接选择排序、堆排序）；

（4）归并排序；

（5）基数排序。

2. 排序的比较

    比较各种排序算法的性能主要是考察各种排序算法的时间复杂度、空间复杂度和稳定性。

排 序

3. JAVA实现

（1）插入排序

    插入排序的算法思想是：在一个有序的元素序列中，不断地将新元素插入到该已经有序的元素列表中的合适位置，直到所有元素都插入到合适位置则完成排序。

<1> 直接插入排序

    直接插入排序的基本思想是：假设前i-1个元素已经有序，将第i个元素的关键字与前i-1个元素的关键字进行比较，找到合适的位置，将第i个元素插入。按照类似的方法，将剩下的元素依次插入到已经有序的序列中，完成插入排序。

示例代码：

/**
 * @author [email protected]
 * 
 *         Time: 2011-8-3 下午12:40:02
 */
public class InsertSort implements Sort {

	/* (non-Javadoc)
	 * @see sort.Sort#sort(int[], java.lang.String)
	 */
	@Override
	public int[] sortArray(int[] data, String sortType) {
		if(data == null || data.length == 0)
			return null;
		if (sortType.equals("asc")) { // 正排序，从小排到大
			// 比较的轮数
			for (int i = 1; i < data.length; i++) {
				// 保证前i+1个数排好序
				int temp = data[i];
				int j;
				for (j = i; j > 0 && data[j - 1] > temp; j--) {
					data[j] = data[j - 1];
				}
				data[j] = temp;
			}
		} else if (sortType.equals("desc")) { // 倒排序，从大排到小
			// 比较的轮数
			for (int i = 1; i < data.length; i++) {
				// 保证前i+1个数排好序
				int temp = data[i];
				int j;
				for (j = i; j > 0 && data[j - 1] < temp; j--) {
					data[j] = data[j - 1];
				}
				data[j] = temp;
			}
		} else {
			System.out.println("您输入的排序类型错误！");
		}
		return data;
	}

}

排 序

图 直接插入排序过程示意图

<2> 折半插入排序

    由于插入排序算法的基本思想是，将待排序元素插入到已经有序的元素序列的正确位置，因此，在查找正确插入位置时，可以采用折半查找的思想寻找插入位置。将这种插入排序称为折半插入排序。

示例代码：

/**
 * @author [email protected]
 *
 * Time: 2011-8-3 下午02:22:23
 */
public class BinInsertSort implements Sort {

	/* (non-Javadoc)
	 * @see sort.Sort#sortArray(int[], java.lang.String)
	 */
	@Override
	public int[] sortArray(int[] data, String sortType) {
		if(data == null || data.length == 0)   
            return null;
		int low = 0,high = 0, mid = 0;
        if (sortType.equals("asc")) { // 正排序，从小排到大   
            // 比较的轮数   
            for (int i = 0; i < data.length -1; i++) {   /* 前i个元素已经有序，从第i+1个元素开始与前i个的有序的关键字比较 */
                // 保证前i+1个数排好序   
                int temp = data[i+1];
                low = 0;
                high = i;
                while(low <= high){                   /*利用折半查找思想寻找当前元素的合适位置 */
                	mid = (low + high) / 2;
                	if(data[mid] > temp) 
                		high = mid - 1;
                	else
                		low = mid + 1;
                }
                int j;   
                for (j = i; j >= low; j--) {           /*移动元素，空出要插入的位置*/
                    data[j+1] = data[j];   
                }
                data[low] = temp;                      /*将当前元素插入合适的位置*/
            }   
        } else if (sortType.equals("desc")) { // 倒排序，从大排到小   
        	// 比较的轮数   
            for (int i = 0; i < data.length -1; i++) {   /* 前i个元素已经有序，从第i+1个元素开始与前i个的有序的关键字比较 */
                // 保证前i+1个数排好序   
                int temp = data[i+1];
                low = 0;
                high = i;
                while(low <= high){                   /*利用折半查找思想寻找当前元素的合适位置 */
                	mid = (low + high) / 2;
                	if(data[mid] < temp) 
                		high = mid - 1;
                	else
                		low = mid + 1;
                }
                int j;   
                for (j = i; j >= low; j--) {           /*移动元素，空出要插入的位置*/
                    data[j+1] = data[j];   
                }
                data[low] = temp;                      /*将当前元素插入合适的位置*/
            }   
        } else {   
            System.out.println("您输入的排序类型错误！");   
        }   
        return data;  
	}

}

<3> 希尔排序

    希尔排序也称为缩小增量排序，它的基本思想是：通过将待排序的元素分为若干个子序列，利用直接插入排序思想对子序列进行排序。然后将该子序列缩小，接着对子序列进行直接插入排序。按照这种思想，直到所有的元素都按照关键字有序排列。

示例代码：

/**
 * @author [email protected]
 *
 * Time: 2011-8-3 下午04:52:35
 */
public class ShellInsertSort implements Sort {

	private int[] delta = {5,3,1};
	/* (non-Javadoc)
	 * @see sort.Sort#sortArray(int[], java.lang.String)
	 */
	@Override
	public int[] sortArray(int[] data, String sortType) {
		/*希尔排序，每次调用算法ShellInsert,delta是存放增量的数组*/
		if(data == null || data.length == 0)   
            return null;
		if(sortType.equals("asc")){
			for(int i=0; i<delta.length; i++){
				shellInsertASC(data,delta[i]);
			}
		}
		else if(sortType.equals("desc")){
			for(int i=0; i<delta.length; i++){
				shellInsertDESC(data,delta[i]);
			}
		}
		else{
			System.out.println("您输入的排序类型错误！");
		}
		return sortData;
	}
	
	private int[] shellInsertASC(int[] data, int c){
		for(int i=c; i<data.length; i++){         /*将距离为c的元素作为一个子序列进行排序*/
			if(data[i] < data[i-c]){                /*如果后者小于前者，则需要移动元素*/
				int temp = data[i];
				int j;
				for(j=i-c; j>=0 && data[j] > temp; j=j-c){
					data[j+c] = data[j];
				}
				data[j+c] = temp;                   /*依次将元素插入到正确的位置*/
			}
		}
		return data;
	}
	
	private int[] shellInsertDESC(int[] data, int c){
		for(int i=c; i<data.length; i++){         /*将距离为c的元素作为一个子序列进行排序*/
			if(data[i] > data[i-c]){                /*如果前者小于后者，则需要移动元素*/
				int temp = data[i];
				int j;
				for(j=i-c; j>=0 && data[j] < temp; j=j-c){
					data[j+c] = data[j];
				}
				data[j+c] = temp;                   /*依次将元素插入到正确的位置*/
			}
		}
		return data;
	}

}

排 序

图 希尔排序过程示意图

（2）交换排序

    交换排序的基本思想是：通过依次交换逆序的元素实现排序。 

<1> 冒泡排序

    冒泡排序的基本思想是：从第一个元素开始，依次比较两个相邻的元素，如果两个元素逆序，则进行交换，即如果L.data[i].key>L.data[i+1].key，则交换L.data[i]与L.data[i+1]。假设元素序列中有

n个待比较的元素，在第一趟排序结束，就会将元素序列中关键字最大的元素移到序列的末尾，即第n个位置。在第二趟排序结束，就会将关键字次大的元素移动到第n-1个位置。

/**
 * @author [email protected]
 * 
 *         Time: 2011-8-3 下午06:38:15
 */
public class BubbleSort implements Sort {

	/*
	 * (non-Javadoc)
	 * 
	 * @see sort.Sort#sortArray(int[], java.lang.String)
	 */
	@Override
	public int[] sortArray(int[] data, String sortType) {
		if (sortType.equals("asc")) { // 正排序，从小排到大
			// 比较的轮数
			for (int i = 1; i < data.length; i++) {
				// 将相邻两个数进行比较，较大的数往后冒泡
				for (int j = 0; j < data.length - i; j++) {
					if (data[j] > data[j + 1]) {
						// 交换相邻两个数
						swap(data, j, j + 1);
					}
				}
			}
		} else if (sortType.equals("desc")) { // 倒排序，从大排到小
			// 比较的轮数
			for (int i = 1; i < data.length; i++) {
				// 将相邻两个数进行比较，较大的数往后冒泡
				for (int j = 0; j < data.length - i; j++) {
					if (data[j] < data[j + 1]) {
						// 交换相邻两个数
						swap(data, j, j + 1);
					}
				}
			}
		} else {
			System.out.println("您输入的排序类型错误！");
		}
		return data;
	}

	private void swap(int[] data, int x, int y) {
		int temp = data[x];
		data[x] = data[y];
		data[y] = temp;
	}

}

  

排 序

图 冒泡排序示意图

<2> 快速排序

    快速排序算法是冒泡排序的一种改进，与冒泡排序类似，只是快速排序是将元素序列中的关键字与指定的元素进行比较，将逆序的两个元素进行交换。快速排序的基本算法思想是：设待排序的元素序列的个数为n，分别存放在数组data[1…n]中，令第一元素作为枢轴元素，即将a[1]作为参考元素，令pivot=a[1]。

/**
 * @author [email protected]
 * 
 *         Time: 2011-8-4 下午12:47:34
 */
public class QuickSort implements Sort {

	/*
	 * (non-Javadoc)
	 * 
	 * @see sort.Sort#sortArray(int[], java.lang.String)
	 */
	@Override
	public int[] sortArray(int[] data, String sortType) {
		if (sortType.equals("asc")) { // 正排序，从小排到大
			qsort_asc(data, 0, data.length - 1);
		} else if (sortType.equals("desc")) { // 倒排序，从大排到小
			qsort_desc(data, 0, data.length - 1);
		} else {
			System.out.println("您输入的排序类型错误！");
		}
		return data;
	}

	/**
	 * 
	 * 快速排序的具体实现，排正序
	 * 
	 * @param data
	 * @param low
	 * @param high
	 */

	private void qsort_asc(int data[], int low, int high) {
		int i, j, x;
		if (low < high) { // 这个条件用来结束递归
			i = low;
			j = high;
			x = data[i];
			while (i < j) {
				while (i < j && data[j] > x) {
					j--; // 从右向左找第一个小于x的数
				}
				if (i < j) {
					data[i] = data[j];
					i++;
				}
				while (i < j && data[i] < x) {
					i++; // 从左向右找第一个大于x的数
				}
				if (i < j) {
					data[j] = data[i];
					j--;
				}
			}
			data[i] = x;
			qsort_asc(data, low, i - 1);
			qsort_asc(data, i + 1, high);
		}
	}

	/**
	 * 
	 * 快速排序的具体实现，排倒序
	 * 
	 * @param data
	 * @param low
	 * @param high
	 */

	private void qsort_desc(int data[], int low, int high) {

		int i, j, x;
		if (low < high) { // 这个条件用来结束递归
			i = low;
			j = high;
			x = data[i];
			while (i < j) {
				while (i < j && data[j] < x) {
					j--; // 从右向左找第一个小于x的数
				}
				if (i < j) {
					data[i] = data[j];
					i++;
				}
				while (i < j && data[i] > x) {
					i++; // 从左向右找第一个大于x的数
				}
				if (i < j) {
					data[j] = data[i];
					j--;
				}
			}
			data[i] = x;
			qsort_desc(data, low, i - 1);
			qsort_desc(data, i + 1, high);
		}
	}
}

排 序

图 快速排序过程示意图

（3）选择排序

    选择排序的基本思想是：从待排序的元素序列中选择关键字最小或最大的元素，将其放在已排序元素序列的最前面或最后面，其余的元素构成新的待排序元素序列，并从待排序元素序列中选择关键字最小的元素，将其放在已排序元素序列的最前面或最后面。 

<1> 简单选择排序

    简单选择排序的基本思想是：假设待排序的元素序列有n个，第一趟排序经过n-1次比较，从n个元素序列中选择关键字最小的元素，并将其放在元素序列的最前面即第一个位置。第二趟排序从剩余的n-1个元素中，经过n-2次比较选择关键字最小的元素，将其放在第二个位置。

/**
 * @author [email protected]
 * 
 *         Time: 2011-8-4 下午04:48:52
 */
public class SelectSort implements Sort {

	/*
	 * (non-Javadoc)
	 * 
	 * @see sort.Sort#sortArray(int[], java.lang.String)
	 */
	@Override
	public int[] sortArray(int[] data, String sortType) {
		if (sortType.equals("asc")) { // 正排序，从小排到大
			int index;
			for (int i = 1; i < data.length; i++) {
				index = 0;
				for (int j = 1; j <= data.length - i; j++) {
					if (data[j] > data[index]) {
						index = j;
					}
				}
				// 交换在位置data.length-i和index(最大值)两个数
				swap(data, data.length - i, index);
			}
		} else if (sortType.equals("desc")) { // 倒排序，从大排到小
			int index;
			for (int i = 1; i < data.length; i++) {
				index = 0;
				for (int j = 1; j <= data.length - i; j++) {
					if (data[j] < data[index]) {
						index = j;
					}
				}
				// 交换在位置data.length-i和index(最大值)两个数
				swap(data, data.length - i, index);
			}
		} else {
			System.out.println("您输入的排序类型错误！");
		}
		return data;
	}

	private void swap(int[] data, int x, int y) {
		int temp = data[x];
		data[x] = data[y];
		data[y] = temp;
	}

}

  

排 序

图 简单选择排序过程示意图

<2> 堆排序

    n个关键字序列Kl，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)：

(1)ki≤K2i且ki≤K2i+1或(2)Ki≥K2i且ki≥K2i+1(1≤i≤[n/2])

    若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。

    根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。

根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆。

注意：

　①堆中任一子树亦是堆。

　②以上讨论的堆实际上是二叉堆(BinaryHeap)，类似地可定义k叉堆。

堆排序(HeapSort)是一树形选择排序。

    堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系【参见二叉树的顺序存储结构】，在当前无序区中选择关键字最大(或最小)的记录。
/**
 * @author [email protected]
 *
 * Time: 2011-8-8 下午04:28:01
 */
public class HeapSort implements Sort {

	/* (non-Javadoc)
	 * @see sort.Sort#sortArray(int[], java.lang.String)
	 */
	@Override
	public int[] sortArray(int[] data, String sortType) {
		if(data == null || data.length == 0){
			return null;
		}
		if(sortType.equals("asc")){
			//该for循环用于创建一个堆，从n/2-1开始向前调整
	        for(int i = data.length/2-1; i>=0; i--){//r.length/2-1为最后一个非终端节点，向前调整
	        	adjustHeapASC(data,i,data.length);
	        }   
	        //该for循环用于把堆顶元素和无序区的最后一个元素交换，成为有序区的第一个元素，并进行堆调整
	        for(int j=data.length-1; j>0; j--){//每次调整出一个元素，则进行n-1趟排序
	            int temp = data[j];
	            data[j] = data[0];
	            data[0] = temp;
	            adjustHeapASC(data,0,j);
	        }
		}
		else if(sortType.equals("desc")){
			//该for循环用于创建一个堆，从n/2-1开始向前调整
	        for(int i = data.length/2-1; i>=0; i--){//r.length/2-1为最后一个非终端节点，向前调整
	        	adjustHeapDESC(data,i,data.length);
	        }   
	        //该for循环用于把堆顶元素和无序区的最后一个元素交换，成为有序区的第一个元素，并进行堆调整
	        for(int j=data.length-1; j>0; j--){//每次调整出一个元素，则进行n-1趟排序
	            int temp = data[j];
	            data[j] = data[0];
	            data[0] = temp;
	            adjustHeapDESC(data,0,j);
	        }
		}
		else{
			System.out.println("您输入的排序类型错误！");
		}
        return data;
	}
	
	private void adjustHeapASC(int[] data,int s,int m){   
        int temp = data[s];//暂存   
        for(int j=2*s+1; j<m; j=j*2){   
            if(j<m-1 && data[j]<data[j+1]){//找出这个根节点的两个子节点中的最大的   
                j++;    //j<m-1防止最后一个只有一个子节点，越界   
            }   
            if(temp > data[j]){//如果该元素已经是最大元素，则不用进行交换，直接跳出循环，自己与自己交换   
                break;   
            }else{//否则，需要进行交换   
            	data[s] = data[j];
                s = j;//s被赋予新值，接着从该节点向下遍历子节点   
            }   
        }   
        data[s] = temp;//一直找到大于或小于两个子节点的时候，把根节点放入该位置   
    }
	
	private void adjustHeapDESC(int[] data,int s,int m){   
        int temp = data[s];//暂存   
        for(int j=2*s+1; j<m; j=j*2){   
            if(j<m-1 && data[j]>data[j+1]){//找出这个根节点的两个子节点中的最大的   
                j++;    //j<m-1防止最后一个只有一个子节点，越界   
            }   
            if(temp < data[j]){//如果该元素已经是最大元素，则不用进行交换，直接跳出循环，自己与自己交换   
                break;   
            }else{//否则，需要进行交换   
            	data[s] = data[j];
                s = j;//s被赋予新值，接着从该节点向下遍历子节点   
            }   
        }   
        data[s] = temp;//一直找到大于或小于两个子节点的时候，把根节点放入该位置   
    }
}

    堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。

堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。

由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。

堆排序是就地排序，辅助空间为O(1)，

    它是不稳定的排序方法。

（4）归并排序

    归并排序(Merge Sort)是利用"归并"技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。

    设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上：R[low..m]，R[m+1..high]，先将它们合并到一个局部的暂存向量R1(相当于输出堆)中，待合并完成后将R1复制回R[low..high]中。

/**
 * @author [email protected]
 * 
 *         Time: 2011-8-8 下午05:49:49
 */
public class MergeSort implements Sort {

	/*
	 * (non-Javadoc)
	 * 
	 * @see sort.Sort#sortArray(int[], java.lang.String)
	 */
	@Override
	public int[] sortArray(int[] data, String sortType) {
		if(data == null || data.length == 0){
			return null;
		}
		gBSort(data,0,data.length-1,sortType); 
		return data;
	}
	
	private void gBSort(int[] data,int low,int high,String sortType){
        if(low<high){//区间长度大于1 
        	int m=(low+high)/2;   
         	gBSort(data,low,m,sortType);   
         	gBSort(data,m+1,high,sortType);
         	if(sortType.equals("asc")){
         		mergeASC(data,data.length,low,m,high);
         	}
         	else if(sortType.equals("desc")){
         		mergeDESC(data,data.length,low,m,high);
         	}
         	else{
         		System.out.println("您输入的排序类型错误！");
         	}
        }   
    }
	private void mergeASC(int[] data, int tempSize, int low, int m, int high) {
		int i = low;
		int j = m + 1;
		int p = 0;
		int[] temp = new int[tempSize];// 动态创建临时的空间
		while (i <= m && j <= high) {
			temp[p++] = (data[i] < data[j]) ? data[i++] : data[j++];// 把小的放到temp中
		}
		while (i <= m) {
			temp[p++] = data[i++];// 把剩余的元素放到临时数组中
		}
		while (j <= high) {
			temp[p++] = data[j++];// 把剩余的元素放到临时数组中
		}
		for (int z = 0, x = low; x <= high; x++, z++) {
			data[x] = temp[z];// 把数组赋值给数组
		}
	}
	
	private void mergeDESC(int[] data, int tempSize, int low, int m, int high) {
		int i = low;
		int j = m + 1;
		int p = 0;
		int[] temp = new int[tempSize];// 动态创建临时的空间
		while (i <= m && j <= high) {
			temp[p++] = (data[i] > data[j]) ? data[i++] : data[j++];// 把小的放到temp中
		}
		while (i <= m) {
			temp[p++] = data[i++];// 把剩余的元素放到临时数组中
		}
		while (j <= high) {
			temp[p++] = data[j++];// 把剩余的元素放到临时数组中
		}
		for (int z = 0, x = low; x <= high; x++, z++) {
			data[x] = temp[z];// 把数组赋值给数组
		}
	}

}

    归并排序是一种稳定的排序。可用顺序存储结构。也易于在链表上实现。对长度为n的文件，需进行 趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序。

（5）基数排序

    基数排序的基本思想是：从低位到高位依次对Kj(j=d-1，d-2，…，0)进行箱排序。在d趟箱排序中，所需的箱子数就是基数rd，这就是"基数排序"名称的由来。

    若排序文件不是以数组R形式给出，而是以单链表形式给出(此时称为链式的基数排序)，则可通过修改出队和人队函数使表示箱子的链队列无须分配结点空间，而使用原链表的结点空间。人队出队操作亦无需移动记录而仅需修改指针。虽然这样一来节省了一定的时间和空间，但算法要复杂得多，且时空复杂度就其数量级而言并未得到改观。

基数排序的时间是线性的(即O(n))。

基数排序所需的辅助存储空间为O(n+rd)。

    基数排序是稳定的。

补充代码：

/**
 * @author [email protected]
 *
 * Time: 2011-8-3 下午01:12:39
 */
public class SortContext {
	private Sort sort;
	/**
     * 初始化测试数组的方法
     * 
     * @return 一个初始化好的数组
     */
	public int[] createArray() {
		Random random = new Random();
		int[] array = new int[10];
		for (int i = 0; i < 10; i++) {
			array[i] = random.nextInt(100) - random.nextInt(100);// 生成两个随机数相减，保证生成的数中有负数
		}
		System.out.println("==========原始序列==========");
		printArray(array);
		return array;
	}

	/**
	 * 
	 * 打印数组中的元素到控制台
	 * 
	 * @param source
	 */

	public void printArray(int[] data) {
		for (int i : data) {
			System.out.print(i + ",");
		}
		System.out.println();
	}
	
	/**
	 * @return the sort
	 */
	public Sort getSort() {
		return sort;
	}

	/**
	 * @param sort the sort to set
	 */
	public void setSort(Sort sort) {
		this.sort = sort;
	}
	
	public void sort(int[] data, String sortType){
		int[] sortData = sort.sortArray(data, sortType);
		printArray(sortData);
	}
}
/**
 * @author [email protected]
 * 
 *         Time: 2011-8-3 下午01:01:10
 */
public class SortTest {
	
	public static void main(String[] args){
		SortContext test = new SortContext();
		int[] data = test.createArray();
		
		test.setSort(new MergeSort());
		//test.setSort(new InsertSort());
		//test.setSort(new BinInsertSort());
		//test.setSort(new QuickSort());
		//test.setSort(new SelectSort());
		//test.setSort(new BubbleSort());
		test.sort(data, "asc");
		test.sort(data, "desc");
	}

}

排序算法稳定性 排序算法

xpsallwell

xpsallwell

0 关注 0 粉丝 0 动态

关注 关注

相关推荐

排序算法

常见的内部排序：插入排序、交换排序、选择排序、归并排序、基数排序外排：归并排序、将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

troysps 2020-07-19

排序—时间复杂度为O(n)的三种排序算法

除此之外，每一个位的数据范围不能太大，要可以用桶排序或者计数排序进行排序，这样基数排序的时间复杂度才为O。例如，我们对10个电话号码进行排序，就可以使用基数排序算法。

路漫 2020-06-16

python中的排序方法

走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。若将两个有序表合并成一个有序表，称为二路归并

只能做防骑 2020-06-09

11.经典O(n2)比较型排序算法

学习算法，除了知道原理以及代码实现以外，还有更重要的是学会如何评价、分析一个排序算法的 执行效率、内存损耗、稳定性。冒泡排序只会操作相邻的两个数据。

wonner 2020-06-04

11.经典O(n2)比较型排序算法

学习算法，除了知道原理以及代码实现以外，还有更重要的是学会如何评价、分析一个排序算法的 执行效率、内存损耗、稳定性。冒泡排序只会操作相邻的两个数据。

wulaxiaohei 2020-06-05

三、排序之冒泡、插入、选择

时间复杂度反应的是数据规模 n 很大的时候的一个增长趋势，所以它表示的时候会忽略系数、常数、低阶。冒泡、插入、选择都是基于比较的排序算法。基于比较的排序算法的执行过程，会涉及两种操作，一种是元素比较大小，另一种是元素交换或移动。所以，如果我们在分析排序算法

wonner 2020-06-03

排序算法(冒泡排序、选择排序、插入排序、快速排序、归并排序）

　　是一种简单的排序算法。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最

清溪算法君老号 2020-06-01

数据结构和算法(Golang实现)(19)排序算法-冒泡排序

冒泡排序是大多数人学的第一种排序算法，在面试中，也是问的最多的一种，有时候还要求手写排序代码，因为比较简单。冒泡排序属于交换类的排序算法。因为小的元素会慢慢地浮到顶端，很像碳酸饮料的汽泡，会冒上去，所以这就是冒泡排序取名的来源。冒泡排序是效率较低的排序算法

rein0 2020-04-18

排序算法-希尔排序

希尔排序的思想：将序列看成一个矩阵，根据一个步长序列将原序列分成m个列，逐列进行排序，直到列数变为1列为止。因此希尔排序的时间复杂度与步长关系密切。举例： 序列元素有32个，那步长序列为 [1, 2, 4, 8, 16]，在进行希尔算法时，按步长从大到时小

Ghero 2020-04-17

归并排序

归并排序与基于交换、选择等排序的思想不一样，“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。故我们将整个算法分为两个部分，一个部分用来进行序列的归并，一个部分用来递归排序。递归排序的算法使用两个边界数来划分递归的区间，每一趟划分都把序列划分为

wulaxiaohei 2020-04-17

选择排序

选择排序的基本思想是：每一趟从待排序列中选取关键字最小的元素，作为有序序列的一个新的元素，直到待排序列只剩下一个元素，则完成排序。主要算法有简单选择排序和堆排序。时间效率：元素移动操作不会超过\次，最好的情况是0次；而元素比较操作则固定有\次，所以时间复杂

shawsun 2020-04-17

选择排序

原始列表： [4104, 8091, 732, 4719, 4860, 4893, 8129, 1410, 8934, 5257]. 选择排序第一次排序需要检查n个元素以寻找最小值，第二次需要检查n-1个，第三次需要检查n-2个。。。排序算法稳定性是指，具

nurvnurv 2020-04-11

基础排序算法—冒泡,插入,选择

wuxiaosi0 2020-04-09

稳定排序和不稳定排序的区别和代表

通俗地讲就是能保证排序前两个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。如果是不稳定排序，则需要第二次排序，会增加系统开销。比较是相邻的两个元素比较，交换也发生在这两个元素之间。基数排序基于分别排序，分别收集，所以其是稳定的排序算法。

ustbfym 2020-04-09

leetcode刷题-- 2. 排序（待更新）

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

wonner 2020-02-22

排序算法之冒泡排序

　　　　　　　　最优时间复杂度O，表示遍历一次没有发现任何可以交换的元素，排序结束。　　　　　　　　最差时间复杂度O. count = 0 #记录内层循环是否进行交换，如果交换，那么加一

baike 2020-02-16

排序--冒泡排序

冒泡排序，是一种计算机科学领域的较简单的排序算法。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端，就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名

ustbfym 2019-12-17

经典排序及总结(python实现)

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。经过某种排序后，如果两个记录序号同等，且两者在原无序记录中的先后秩序依然保持不变，则称所使用的排序方法是稳定的，反之是不稳

wuxiaosi0 2019-12-10

面试中可能被问到的常用排序算法

排序算法是一种比较简单的算法，从我们一开始接触计算机编程开始接触的可能就是排序或者搜索一类的算法，但是因为排序在其他的一些算法中应用较多，所以为了提高性能已经研究了多种排序算法。目前区别排序算法主要还是以时间复杂度，空间复杂度，稳定性等来排序，接下来我们分

Broadview 2019-11-19

动画 | 大学四年结束之前必须透彻的排序算法

现如今大学生学习排序算法，除了学习它的算法原理、代码实现之外，作为一个大学生更重要的往往是要学会如何评价、分析一个排序算法。排序对于任何一个程序员来说，可能都不会陌生。大部分编程语言中，也都提供了排序函数。本章主要从如何分析一个算法开始入手，从而循进渐进的

风吹夏天 2019-11-12
xpsallwell

xpsallwell

W3CSchool教程
HTML 教程
CSS 教程
Bootstrap 教程
Javascript 教程
jQuery 教程
后端教程
C 教程
Java 教程
PHP 教程
Python 教程
Go 教程
移动开发
Android 教程
Swift 教程
Kotlin 教程
jQuery Mobile 教程
ionic 教程
关于我们
新闻动态
联系方式
招聘英才
安科实验室
帮助与反馈

安科网(Ancii)，中国第一极客网

Copyright © 2013 - 2019 Ancii.com

京ICP备18063983号 京公网安备11010802014868号