学习路上的排序

1>比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2>每趟从第一对相邻元素开始，对每一对相邻元素作同样的工作，直到最后一对。
3>针对所有的元素重复以上的步骤，除了已排序过的元素(每趟排序后的最后一个元素)，直到没有任何一对数字需要比较。

经过  i次扫描后，数列的末尾 i 项必然是最大的 i 项，因此冒泡排序最多需要扫描  n-1遍数组就能完成排序。

时间复杂度：

在序列完全有序时，冒泡排序只需遍历一遍数组，不用执行任何交换操作，时间复杂度为 O(n)。

在最坏情况下，冒泡排序要执行  (n-1)n/2次交换操作，时间复杂度为 O(n^2)。

冒泡排序的平均时间复杂度为 O(n^2)。

稳定性：

  在冒泡排序中，遇到相等的值，是不进行交换的，只有遇到不相等的值才进行交换，所以是稳定的排序方式。

 #include 
void bubble (int a[ ], int n);
int main()
{    
  int n, a[10];
    
    scanf("%d", &n);
    
    for (int i=0; i<=n-1;i++)
        scanf("%d",&a[i]);
        
    bubble(a,n);//冒泡函数调用 
    
    for (int i=0; i<=n-1;i++)
        printf("%d ",a[i]);
    return 0;
}
 void bubble (int a[ ], int n)
 {
    int t;
    for(int i=0;ia[j])
			{
                t=a[i];
                a[i]=a[j];
                a[j]=t;
            }
        }
    }
}

或者写成这样

//初始化的时候从a[1]开始
 void bubble (int a[ ], int n)
 {
    int t;
    for(int i=1;i<=n-1;i++)
	{
        for(int j=1;j<=n-i;j++)
		{
            if(a[j]>a[j+1])
			{
                t=a[j];
                a[j]=a[j+1];
                a[j+1]=t;
            }
        }
    }
}

 外循环优化

如果某次比较过程中，发现没有任何元素移动，则不再进行接下来的比较。

//初始化的时候从a[1]开始
 void bubble (int a[ ], int n)
 {
    int t;
   bool flag; //用来判断该趟是否有元素交换； 
    for(int i=1;i<=n-1;i++)
	{
		flag=false;
        for(int j=1;j<=n-i;j++)
		{
            if(a[j]>a[j+1])
			{
				flag=true;//发生交换进行更新 
                t=a[j];
                a[j]=a[j+1];
                a[j+1]=t;
            }
        
        }
    if(!flag)break;
    }
}

内循环优化

     外循环优化方式，只能在“趟”的级别上优化。
  内循环优化方式，也就是要实现在“次”的级别进行优化，其思路是“记下最后一次交换的位置，后边没有交换，必然是有序的，然后下一次排序从第一个比较到上次记录的位置结束即可”。
 

 void bubble (int a[ ], int n)
 {
    int t;
   bool flag; //用来判断该趟是否有元素交换； 
   int p=n-1; 
    for(int i=1;i<=n-1;i++)
	{
		int np=0;//用来记录每次交换的位置 
		flag=false;
        for(int j=1;j<=p;j++)
		{
            if(a[j]>a[j+1])
			{
				flag=true;//发生交换进行更新 
                t=a[j];
                a[j]=a[j+1];
                a[j+1]=t;
                np=j;
                
            }
          
        }
        if(!flag)break;
         p=np;
    }
}

双向遍历 

2.选择排序

它的工作原理是每次找出第 i小的元素（也就是 a 中最小的元素），然后将这个元素与数组第 i 个位置上的元素交换。

时间复杂度:

  选择排序的时间复杂度为O(n^2)。

稳定性:

由于 swap（交换两个元素）操作的存在，选择排序是一种不稳定的排序算法。

#include

void selection(int a[], int n)
 {
  for (int i = 1; i < n; i++)
   {
    int ith = i;//
    for (int j = i + 1; j <= n; ++j) 
	{
      if (a[j] < a[ith])
	   {
        ith = j;//记录最小的数的位置 
      }
    }
    //进行交换 
    int t = a[i];
    a[i] = a[ith];
    a[ith] = t;
  }
}
int main()
{
	int a[10001];
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	scanf("%d",&a[i]); 
	selection(a,n);
	for(int i=1;i<=n;i++)
	printf("%d ",a[i]);
	return 0;
 } 

同时查找最大和最小优化 

选择排序的优化思路一般是在一趟遍历中，同时找出最大值与最小值，放到数组两端，这样就能将遍历的趟数减少一半。

 void selection(int a[],int n)
{
      
     int left = 1;
     int right = n;
     while (left < right)
     {
      
         int min = left;
         int max = right;
         for (int i = left; i <= right; i++)
        {
          
             if (a[i] < a[min])
                 min = i;
             if (a[i] > a[max])
                 max = i;
         }
         
         int temp = a[max];
         a[max] = a[right];
         a[right] = temp;
         
         if (min == right)
             min = max;
         
         temp = a[min];
         a[min] = a[left];
         a[left] = temp;
         
         left++;
         right--;
     }
}

3.插入排序