Ⅰ 常见的排序算法—选择，冒泡，插入，快速，归并
太久没看代码了，最近打算复习一下java，又突然想到了排序算法，就把几种常见的排序算法用java敲了一遍，这里统一将无序的序列从小到大排列。
选择排序是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小元素，继续放在下一个位置，直到待排序元素个数为0。
选择排序代码如下：
public void Select_sort(int[] arr) {
int temp,index;
for( int i=0;i<10;i++) {
index = i;
for(int j = i + 1 ; j < 10 ; j++) {
if(arr[j] < arr[index])
index = j;
}
/*
temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
*/
swap(arr,i,index);
}
System.out.print("经过选择排序后：");
for(int i = 0 ; i < 10 ; i++)
System.out.print( arr[i] +" ");
System.out.println("");
}
冒泡排序是一种比较基础的排序算法，其思想是相邻的元素两两比较，较大的元素放后面，较小的元素放前面，这样一次循环下来，最大元素就会归位，若数组中元素个数为n，则经过（n-1）次后，所有元素就依次从小到大排好序了。整个过程如同气泡冒起，因此被称作冒泡排序。
选择排序代码如下：
public void Bubble_sort(int[] arr) {
int temp;
for(int i = 0 ; i < 9 ; i++) {
for(int j = 0 ; j < 10 - i - 1 ;j++) {
if(arr[j] > arr[j+1]) {
/*
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
*/
swap(arr,j,j+1);
}
}
}
System.out.print("经过冒泡排序后：");
for(int i = 0 ; i < 10 ; i++)
System.out.print( arr[i] +" ");
System.out.println("");
}
插入排序也是一种常见的排序算法，插入排序的思想是：创建一个与待排序数组等大的数组，每次取出一个待排序数组中的元素，然后将其插入到新数组中合适的位置，使新数组中的元素保持从小到大的顺序。
插入排序代码如下：
public void Insert_sort(int[] arr) {
int length = arr.length;
int[] arr_sort = new int[length];
int count = 0;
for(int i = 0;i < length; i++) {
if(count == 0) {
arr_sort[0] = arr[0];
}else if(arr[i] >= arr_sort[count - 1]) {
arr_sort[count] = arr[i];
}else if(arr[i] < arr_sort[0]) {
insert(arr,arr_sort,arr[i],0,count);
}else {
for(int j = 0;j < count - 1; j++) {
if(arr[i] >= arr_sort[j] && arr[i] < arr_sort[j+1]) {
insert(arr,arr_sort,arr[i],j+1,count);
break;
}
}
}
count++;
}
System.out.print("经过插入排序后：");
for(int i = 0 ; i < 10 ; i++)
System.out.print( arr_sort[i] +" ");
System.out.println("");
}
public void insert(int[] arr,int[] arr_sort,int value,int index,int count) {
for(int i = count; i > index; i--)
arr_sort[i] = arr_sort[i-1];
arr_sort[index] = value;
}
快速排序的效率比冒泡排序算法有大幅提升。因为使用冒泡排序时，一次外循环只能归位一个值，有n个元素最多就要执行（n-1）次外循环。而使用快速排序时，一次可以将所有元素按大小分成两堆，也就是平均情况下需要logn轮就可以完成排序。
快速排序的思想是：每趟排序时选出一个基准值（这里以首元素为基准值），然后将所有元素与该基准值比较，并按大小分成左右两堆，然后递归执行该过程，直到所有元素都完成排序。
public void Quick_sort(int[] arr, int left, int right) {
if(left >= right)
return ;
int temp,t;
int j = right;
int i = left;
temp = arr[left];
while(i < j) {
while(arr[j] >= temp && i < j)
j--;
while(arr[i] <= temp && i < j)
i++;
if(i < j) {
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
arr[left] = arr[i];
arr[i] = temp;
Quick_sort(arr,left, i - 1);
Quick_sort(arr, i + 1, right);
}
归并排序是建立在归并操作上的一种有效的排序算法，归并排序对序列的元素进行逐层折半分组，然后从最小分组开始比较排序，每两个小分组合并成一个大的分组，逐层进行，最终所有的元素都是有序的。
public void Mergesort(int[] arr,int left,int right) {
if(right - left > 0) {
int[] arr_1 = new int[(right - left)/2 + 1];
int[] arr_2 = new int[(right - left + 1)/2];
int j = 0;
int k = 0;
for(int i = left;i <= right;i++) {
if(i <= (right + left)/2) {
arr_1[j++] = arr[i];
}else {
arr_2[k++] = arr[i];
}
}
Mergesort(arr_1,0,(right - left)/2);
Mergesort(arr_2,0,(right - left - 1)/2);
Merge(arr_1,arr_2,arr);
}
}
public void Merge(int[] arr_1,int[] arr_2,int[] arr) {
int i = 0;
int j = 0;
int k = 0;
int L1 = arr_1.length;
int L2 = arr_2.length;
while(i < L1 && j < L2) {
if(arr_1[i] <= arr_2[j]) {
arr[k] = arr_1[i];
i++;
}else {
arr[k] = arr_2[j];
j++;
}
k++;
}
if(i == L1) {
for(int t = j;j < L2;j++)
arr[k++] = arr_2[j];
}else {
for(int t = i;i < L1;i++)
arr[k++] = arr_1[i];
}
}
归并排序这里我使用了left，right等变量，使其可以通用，并没有直接用数字表示那么明确，所以给出相关伪代码，便于理解。
Mergesort(arr[0...n-1])
//输入：一个可排序数组arr[0...n-1]
//输出：非降序排列的数组arr[0...n-1]
if n>1
arr[0...n/2-1] to arr_1[0...(n+1)/2-1]//确保arr_1中元素个数>=arr_2中元素个数
//对于总个数为奇数时，arr_1比arr_2中元素多一个；对于总个数为偶数时，没有影响
arr[n/2...n-1] to arr_2[0...n/2-1]
Mergesort(arr_1[0...(n+1)/2-1])
Mergesort(arr_2[0...n/2-1])
Merge(arr_1,arr_2,arr)
Merge(arr_1[0...p-1],arr_2[0...q-1],arr[0...p+q-1])
//输入：两个有序数组arr_1[0...p-1]和arr_2[0...q-1]
//输出：将arr_1与arr_2两数组合并到arr
int i<-0;j<-0;k<-0
while i
<p span="" do<="" jif arr_1[i] <= arr_2[j]
arr[k] <- arr_1[i]
i<-i+1
else arr[k] <- arr_2[j];j<-j+1
k<-k+1
if i=p
arr_2[j...q-1] to arr[k...p+q-1]
else arr_1[i...p-1] to arr[k...p+q-1]
package test_1;
import java.util.Scanner;
public class Test01 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] arr_1 = new int[10];
for(int i = 0 ; i < 10 ; i++)
arr_1[i] = sc.nextInt();
Sort demo_1 = new Sort();
//1~5一次只能运行一个，若多个同时运行，则只有第一个有效，后面几个是无效排序。因为第一个运行的已经将带排序数组排好序。
demo_1.Select_sort(arr_1);//-----------------------1
//demo_1.Bubble_sort(arr_1);//---------------------2
/* //---------------------3
demo_1.Quick_sort(arr_1, 0 , arr_1.length - 1);
System.out.print("经过快速排序后：");
for(int i = 0 ; i < 10 ; i++)
System.out.print( arr_1[i] +" ");
System.out.println("");
*/
//demo_1.Insert_sort(arr_1);//--------------------4
/* //--------------------5
demo_1.Mergesort(arr_1,0,arr_1.length - 1);
System.out.print("经过归并排序后：");
for(int i = 0 ; i < 10 ; i++)
System.out.print( arr_1[i] +" ");
System.out.println("");
*/
}
}
class Sort {
public void swap(int arr[],int a, int b) {
int t;
t = arr[a];
arr[a] = arr[b];
arr[b] = t;
}
public void Select_sort(int[] arr) {
int temp,index;
for( int i=0;i<10;i++) {
index = i;
for(int j = i + 1 ; j < 10 ; j++) {
if(arr[j] < arr[index])
index = j;
}
/*
temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
*/
swap(arr,i,index);
}
System.out.print("经过选择排序后：");
for(int i = 0 ; i < 10 ; i++)
System.out.print( arr[i] +" ");
System.out.println("");
}
public void Bubble_sort(int[] arr) {
int temp;
for(int i = 0 ; i < 9 ; i++) {
for(int j = 0 ; j < 10 - i - 1 ;j++) {
if(arr[j] > arr[j+1]) {
/*
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
*/
swap(arr,j,j+1);
}
}
}
System.out.print("经过冒泡排序后：");
for(int i = 0 ; i < 10 ; i++)
System.out.print( arr[i] +" ");
System.out.println("");
}
public void Quick_sort(int[] arr, int left, int right) {
if(left >= right)
return ;
int temp,t;
int j = right;
int i = left;
temp = arr[left];
while(i < j) {
while(arr[j] >= temp && i < j)
j--;
while(arr[i] <= temp && i < j)
i++;
if(i < j) {
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
arr[left] = arr[i];
arr[i] = temp;
Quick_sort(arr,left, i - 1);
Quick_sort(arr, i + 1, right);
}
public void Insert_sort(int[] arr) {
int length = arr.length;
int[] arr_sort = new int[length];
int count = 0;
for(int i = 0;i < length; i++) {
if(count == 0) {
arr_sort[0] = arr[0];
}else if(arr[i] >= arr_sort[count - 1]) {
arr_sort[count] = arr[i];
}else if(arr[i] < arr_sort[0]) {
insert(arr,arr_sort,arr[i],0,count);
}else {
for(int j = 0;j < count - 1; j++) {
if(arr[i] >= arr_sort[j] && arr[i] < arr_sort[j+1]) {
insert(arr,arr_sort,arr[i],j+1,count);
break;
}
}
}
count++;
}
System.out.print("经过插入排序后：");
for(int i = 0 ; i < 10 ; i++)
System.out.print( arr_sort[i] +" ");
System.out.println("");
}
public void insert(int[] arr,int[] arr_sort,int value,int index,int count) {
for(int i = count; i > index; i--)
arr_sort[i] = arr_sort[i-1];
arr_sort[index] = value;
}
public void Mergesort(int[] arr,int left,int right) {
if(right - left > 0) {
int[] arr_1 = new int[(right - left)/2 + 1];
int[] arr_2 = new int[(right - left + 1)/2];
int j = 0;
int k = 0;
for(int i = left;i <= right;i++) {
if(i <= (right + left)/2) {
arr_1[j++] = arr[i];
}else {
arr_2[k++] = arr[i];
}
}
Mergesort(arr_1,0,(right - left)/2);
Mergesort(arr_2,0,(right - left - 1)/2);
Merge(arr_1,arr_2,arr);
}
}
public void Merge(int[] arr_1,int[] arr_2,int[] arr) {
int i = 0;
int j = 0;
int k = 0;
int L1 = arr_1.length;
int L2 = arr_2.length;
while(i < L1 && j < L2) {
if(arr_1[i] <= arr_2[j]) {
arr[k] = arr_1[i];
i++;
}else {
arr[k] = arr_2[j];
j++;
}
k++;
}
if(i == L1) {
for(int t = j;j < L2;j++)
arr[k++] = arr_2[j];
}else {
for(int t = i;i < L1;i++)
arr[k++] = arr_1[i];
}
}
}
若有错误，麻烦指正，不胜感激。
Ⅱ 算法的五个重要特性
算法的五大特性：
1、输入: 算法具有0个或多个输入。
2、输出: 算法至少有1个或多个输出。
3、有穷性: 算法在有限的步骤之后会自动结束而不会无限循环，并且每- 一个步骤可以在可接受的时间内完成。
4、确定性：算法中的每一步都有确定的含义，不会出现二义性。
5、可行性：算法的每一步都是可行的，也就是说每一步都能够执行有限的次数完。
拓展资料：
算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。
Ⅲ 归并排序算法：用两路归并算法，实现N个无素的排序
合并排序（MERGE SORT）是又一类不同的排序方法，合并的含义就是将两个或两个以上的有序数据序列合并成一个新的有序数据序列，因此它又叫归并算法。它的基本思想就是假设数组A有N个元素，那么可以看成数组A是又N个有序的子序列组成，每个子序列的长度为1，然后再两两合并，得到了一个 N/2 个长度为2或1的有序子序列，再两两合并，如此重复，值得得到一个长度为N的有序数据序列为止，这种排序方法称为2—路合并排序。
例如数组A有7个数据，分别是： 49 38 65 97 76 13 27，那么采用归并排序算法的操作过程如图7所示：
初始值 [49] [38] [65] [97] [76] [13] [27]
看成由长度为1的7个子序列组成
第一次合并之后 [38 49] [65 97] [13 76] [27]
看成由长度为1或2的4个子序列组成
第二次合并之后 [38 49 65 97] [13 27 76]
看成由长度为4或3的2个子序列组成
第三次合并之后 [13 27 38 49 65 76 97]
合并算法的核心操作就是将一维数组中前后相邻的两个两个有序序列合并成一个有序序列。合并算法也可以采用递归算法来实现，形式上较为简单,但实用性很差。合并算法的合并次数是一个非常重要的量,根据计算当数组中有3到4个元素时,合并次数是2次,当有5到8个元素时,合并次数是3次,当有9到16个元素时,合并次数是4次，按照这一规律,当有N个子序列时可以推断出合并的次数是X(2 >=N,符合此条件的最小那个X)。
其时间复杂度为：O(nlogn).所需辅助存储空间为：O(n)
归并算法如下：
long merge(long *A,long p,long q,long r)
{
long n1,n2,i,j,k;
long *L,*R;
n1=q-p+1;
n2=r-q;
L=(long *)malloc((n1+2)*sizeof(long));
R=(long *)malloc((n2+2)*sizeof(long));
for(i=1;i<=n1;i++)
L=A[p+i-1];
for(j=1;j<=n2;j++)
R[j]=A[q+j];
L[n1+1]=R[n2+1]=RAND_MAX;
i=j=1;
for(k=p;k<=r;k++)
{
if(L<=R[j])
{
A[k]=L;
i++;
}
else
{
A[k]=R[j];
j++;
}
}
free(L);
free(R);
return 0;
}
long mergesort(long *A,long p,long r)
{
long q;
if(p<r)
{
q=(p+r)/2;
mergesort(A,p,q);
mergesort(A,q+1,r);
merge(A,p,q,r);
}
return 0;
}
Ⅳ 程序员都应该精通的六种算法，你会了吗
对于一名优秀的程序员来说，面对一个项目的需求的时候，一定会在脑海里浮现出最适合解决这个问题的方法是什么，选对了算法，就会起到事半功倍的效果，反之，则可能会使程序运行效率低下，还容易出bug。因此，熟悉掌握常用的算法，是对于一个优秀程序员最基本的要求。
那么，常用的算法都有哪些呢？一般来讲，在我们日常工作中涉及到的算法，通常分为以下几个类型：分治、贪心、迭代、枚举、回溯、动态规划。下面我们来一一介绍这几种算法。
一、分治算法
分治算法，顾名思义，是将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
分治算法一般分为三个部分：分解问题、解决问题、合并解。
分治算法适用于那些问题的规模缩小到一定程度就可以解决、并且各子问题之间相互独立，求出来的解可以合并为该问题的解的情况。
典型例子比如求解一个无序数组中的最大值，即可以采用分治算法，示例如下：
def pidAndConquer(arr,leftIndex,rightIndex):
if(rightIndex==leftIndex+1 || rightIndex==leftIndex){
return Math.max(arr[leftIndex],arr[rightIndex]);
}
int mid=(leftIndex+rightIndex)/2;
int leftMax=pidAndConquer(arr,leftIndex,mid);
int rightMax=pidAndConquer(arr,mid,rightIndex);
return Math.max(leftMax,rightMax);
二、贪心算法
贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
贪心算法的基本思路是把问题分成若干个子问题，然后对每个子问题求解，得到子问题的局部最优解，最后再把子问题的最优解合并成原问题的一个解。这里要注意一点就是贪心算法得到的不一定是全局最优解。这一缺陷导致了贪心算法的适用范围较少，更大的用途在于平衡算法效率和最终结果应用，类似于：反正就走这么多步，肯定给你一个值，至于是不是最优的，那我就管不了了。就好像去菜市场买几样菜，可以经过反复比价之后再买，或者是看到有卖的不管三七二十一先买了，总之最终结果是菜能买回来，但搞不好多花了几块钱。
典型例子比如部分背包问题：有n个物体，第i个物体的重量为Wi，价值为Vi，在总重量不超过C的情况下让总价值尽量高。每一个物体可以只取走一部分，价值和重量按比例计算。
贪心策略就是，每次都先拿性价比高的，判断不超过C。
三、迭代算法
迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程。迭代算法是用计算机解决问题的一种基本方法，它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令(或一定步骤)进行重复执行，在每次执行这组指令(或这些步骤)时，都从变量的原值推出它的一个新值。最终得到问题的结果。
迭代算法适用于那些每步输入参数变量一定，前值可以作为下一步输入参数的问题。
典型例子比如说，用迭代算法计算斐波那契数列。
四、枚举算法
枚举算法是我们在日常中使用到的最多的一个算法，它的核心思想就是:枚举所有的可能。枚举法的本质就是从所有候选答案中去搜索正确地解。
枚举算法适用于候选答案数量一定的情况。
典型例子包括鸡钱问题，有公鸡5，母鸡3，三小鸡1，求m钱n鸡的所有可能解。可以采用一个三重循环将所有情况枚举出来。代码如下：
五、回溯算法
回溯算法是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
典型例子是8皇后算法。在8 8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问一共有多少种摆法。
回溯法是求解皇后问题最经典的方法。算法的思想在于如果一个皇后选定了位置，那么下一个皇后的位置便被限制住了，下一个皇后需要一直找直到找到安全位置，如果没有找到，那么便要回溯到上一个皇后，那么上一个皇后的位置就要改变，这样一直递归直到所有的情况都被举出。
六、动态规划算法
动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。
动态规划算法适用于当某阶段状态给定以后，在这阶段以后的过程的发展不受这段以前各段状态的影响，即无后效性的问题。
典型例子比如说背包问题，给定背包容量及物品重量和价值，要求背包装的物品价值最大。
Ⅳ C++镞犲簭鏁扮粍鍞涓鍖杁eplicate绠楁硶锛岃佹眰镞堕棿澶嶆潅搴︿负O锛坣logn锛
鍏堟帓搴忥纴澶嶆潅搴︿负O(n log n)锛岀劧钖庡幓閲嶏纴涔熷氨鏄铡绘帀鐩搁偦镄勭浉钖屽厓绱犲嵆鍙锛屽嶆潅搴O(n)锛屾晠镐荤殑澶嶆潅搴︿负O(n log n)銆
int a[10] = {***};
sort(&a[0], &a[10]);
int* b = unique(&a[0], &a[10]);
鍒*a, *(a+1)鍒*(b-1)涓烘棤閲岖殑鍏幂礌銆俿ort鍜寀nique鍧囦负STL镄勭畻娉曪纴澶存枃浠禷lgorithm銆