各大排序算法再次整理

冒泡排序

/*
原理是相邻的数两两交换,按照从小到大或者从大到小的顺序进行交换,

这样一趟过去后,最大或最小的数字被交换到了最后一位,

然后再从头开始进行两两比较交换,直到倒数第二位时结束；
*/

#include<stdio.h>
#include<iostream>
using namespace std;

void Bubble_sort(int a[], int n)
{
int i, j;
int temp;
//所有排序完整
for (i = 0; i < n-1 ; i++)
{
for (j = 0; j < n-1-i ; j++)
{
if (a[j]>a[j+1])
{
temp = a[j];
a[j] = a[j+1];
a[j+1]= temp;
}
}
}
//一趟排序后的结果
/*    for (j = 0; j < n-1; j++)
{
if (a[j]>a[j+1])
{
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}*/
}
int main()
{
int a[101];
int n,i,j;
cin >> n;
for (i = 0; i < n; i++)
cin >> a[i];
Bubble_sort(a, n);
for (i = 0; i < n; i++)
cout << a[i] << " ";
cout<<endl;
return 0;
}

//由于冒泡排序算法本身就是一种低效算法，即使判断了在某种条件下已经排序好直接退出，也是十分的耗时

简单选择排序

/*
选择排序:每趟从待排序部分[i,n]中选择最小的元素，
令其与待排序部分的第一个元素A[i]进行交换，这样元
素A[i]就会与当前有序区间[1,i-1]形成新的有序区间[1,i]
于是在n趟操作后，所有元素就会是有序的。
总共进行n趟操作，算法复杂度：O(n^2)
*/

#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;

void slect_sort(int a[],int n)
{
int i, j, k,temp;
for (i = 0; i < n; i++)//进行n趟操作
{
k = i;
for (j = i; j < n; j++)//选出[i,n]中最小的元素，下标为k
{
if (a[j] < a[k])
{
k = j;
}
}
temp = a[i];//交换a[k]与a[i]
a[i] = a[k];
a[k] = temp;
}
}
int main()
{
int num[50];
int N,i;
cin >> N;
for (i = 0; i < N; i++)
cin >> num[i];
slect_sort(num, N);
for (i = 0; i < N; i++)
cout << num[i]<<" ";
cout << endl;
return 0;

}

 直接插入排序

/*
直接插入排序:每趟从范围[i，i-1]中寻找某个位置j，（此时A[j]~a[i-1]会后移一位至A[j+1]~A[i]）
使得将A[i]插入位置j后，范围[1,i]有序。
总共进行n-1趟操作，算法复杂度：O(n^2)
*/

#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;

void insert_sort(int  a[],int n)
{
    int i, j, k,temp;
    for (i = 1; i < n; i++)//进行n-1趟排序操作
    {
        temp=a[i];//temp临时存放A[i],
        j = i;//j从i开始往前枚举
        while (j>0 && temp < a[j - 1])//只要temp小于签一份元素A[j-1]
        {
            a[j] = a[j - 1];//把A[j-1]后移动一位至a[j]
            j--;
        }
        a[j] = temp;//插入位置为j
    }
}
int main()
{
    int num[50];
    int N,i;
    cin >> N;
    for (i = 0; i < N; i++)
        cin >> num[i];
    insert_sort(num, N);
    for (i = 0; i < N; i++)
        cout << num[i]<<" ";
    cout << endl;
    return 0;

}

快速排序

/*

 快速排序具有最好的平均性能（average behavior），但最坏性能（worst case behavior）和插入排序

相同，也是O(n^2)。比如一个序列5,4,3,2,1，要排为1,2,3,4,5。按照快速排序方法，每次只会有一个数据进入正确顺序，不能把数据分成大小相当的两份，很明显，排序的过程就成了一个歪脖子树，树的深度为n，那时间复杂度就成了O(n^2)。尽管如此，需要排序的情况几乎都是乱序的，自然性能就保证了。据书上的测试图来看，在数据量小于20的时候，插入排序具有最好的性能。当大于20时，快速排序具有最好的性能，归并(merge sort)和堆排序(heap sort)也望尘莫及，尽管复杂度都为nlog2(n)。
1、算法思想
    　快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

（1） 分治法的基本思想
    　分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

（2）快速排序的基本思想
    　设当前待排序的无序区为R[low..high]，利用分治法可将快速排序的基本思想描述为：
①分解： 
    　在R[low..high]中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。
  注意：
    　划分的关键是要求出基准记录所在的位置pivotpos。划分的结果可以简单地表示为(注意pivot=R[pivotpos])：
    　R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys
                  其中low≤pivotpos≤high。
②求解： 
   　 通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。

③组合： 
    　因为当"求解"步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言，"组合"步骤无须做什么，可看作是空操作。

2、快速排序算法QuickSort
  void QuickSort(SeqList R，int low，int high)
   { //对R[low..high]快速排序
     int pivotpos； //划分后的基准记录的位置
     if(low<high){//仅当区间长度大于1时才须排序
        pivotpos=Partition(R，low，high)； //对R[low..high]做划分
        QuickSort(R，low，pivotpos-1)； //对左区间递归排序
        QuickSort(R，pivotpos+1，high)； //对右区间递归排序
      }
    } //QuickSort

*/

#include<iostream>
#include<cstdio>
#include <cstring>  
#include<math.h>
#include<algorithm>
using namespace std;

void quick_sort(int a[], int low,int high)
{
    if (low >= high)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
    {
        return;
    }
    int first, last, key;
    first = low;
    last = high;
    key = a[first];/*用字表的第一个记录作为枢轴*/
    while (first < last) /*控制在当组内寻找一遍*/
    {
        while (first < last&&a[last] >= key) /*而寻找结束的条件就是，1，找到一个小于或者大于key的数（大于或小于取决于你想升
                                             序还是降序）2，没有符合条件1的，并且i与j的大小没有反转*/
        {

            last--;/*向前寻找*/
        }
        a[first] = a[last]; /*找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是
                            a[left]，那么就是给key）*/
        while (first < last&&a[first] <= key)  /*这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，
                                               因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反*/
        {
            first++;
        }
        a[last] = a[first];
    }
    a[first] = key;/*当在当组内找完一遍以后就把中间数key回归*/
    quick_sort(a, low, first - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/
    quick_sort(a, first + 1, high);/*用同样的方式对分出来的右边的小组进行同上的做法*/
                       /*当然最后可能会出现很多分左右，直到每一组的i = j 为止*/
}


int main()
{
    int a[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
    quick_sort(a, 0,8);
    int i;
    for (i = 0; i < 9; i++)
        printf("%d
", a[i]);
        return 0;
}