搜索旋轉排序數組演算法

1. 快速排序演算法原理與實現

快速排序的基本思想就是從一個數組中任意挑選一個元素（通常來說會選擇最左邊的元素）作為中軸元素，將剩下的元素以中軸元素作為比較的標准，將小於等於中軸元素的放到中軸元素的左邊，將大於中軸元素的放到中軸元素的右邊。

然後以當前中軸元素的位置為界，將左半部分子數組和右半部分子數組看成兩個新的數組，重復上述操作，直到子數組的元素個數小於等於1（因為一個元素的數組必定是有序的）。

以下的代碼中會常常使用交換數組中兩個元素值的Swap方法，其代碼如下

publicstaticvoidSwap(int[] A, inti, intj){

inttmp;

tmp = A[i];

A[i] = A[j];

A[j] = tmp;

(1)搜索旋轉排序數組演算法擴展閱讀：

快速排序演算法 的基本思想是：將所要進行排序的數分為左右兩個部分，其中一部分的所有數據都比另外一 部分的數據小，然後將所分得的兩部分數據進行同樣的劃分，重復執行以上的劃分操作，直 到所有要進行排序的數據變為有序為止。

定義兩個變數low和high，將low、high分別設置為要進行排序的序列的起始元素和最後一個元素的下標。第一次，low和high的取值分別為0和n-1，接下來的每次取值由劃分得到的序列起始元素和最後一個元素的下標來決定。

定義一個變數key，接下來以key的取值為基準將數組A劃分為左右兩個部分，通 常，key值為要進行排序序列的第一個元素值。第一次的取值為A[0]，以後毎次取值由要劃 分序列的起始元素決定。

從high所指向的數組元素開始向左掃描，掃描的同時將下標為high的數組元素依次與劃分基準值key進行比較操作，直到high不大於low或找到第一個小於基準值key的數組元素，然後將該值賦值給low所指向的數組元素，同時將low右移一個位置。

如果low依然小於high，那麼由low所指向的數組元素開始向右掃描，掃描的同時將下標為low的數組元素值依次與劃分的基準值key進行比較操作，直到low不小於high或找到第一個大於基準值key的數組元素，然後將該值賦給high所指向的數組元素，同時將high左移一個位置。

重復步驟(3) (4)，直到low的植不小於high為止，這時成功劃分後得到的左右兩部分分別為A[low……pos-1]和A[pos+1……high]，其中，pos下標所對應的數組元素的值就是進行劃分的基準值key，所以在劃分結束時還要將下標為pos的數組元素賦值 為 key。

2. 幾種常見的查找演算法之比較

二分法平均查找效率是O(logn)，但是需要數組是排序的。如果沒有排過序，就只好先用O（nlogn)的預處理為它排個序了。而且它的插入比較困難，經常需要移動整個數組，所以動態的情況下比較慢。

哈希查找理想的插入和查找效率是O(1)，但條件是需要找到一個良好的散列函數，使得分配較為平均。另外，哈希表需要較大的空間，至少要比O(n)大幾倍，否則產生沖突的概率很高。

二叉排序樹查找也是O(logn)的，關鍵是插入值時需要做一些處理使得它較為平衡（否則容易出現輕重的不平衡，查找效率最壞會降到O(n)），而且寫起來稍微麻煩一些，具體的演算法你可以隨便找一本介紹數據結構的書看看。當然，如果你用的是c語言，直接利用它的庫類型map、multimap就可以了,它是用紅黑樹實現的，理論上插入、查找時間都是O(logn)，很方便，不過一般會比自己實現的二叉平衡樹稍微慢一些。

3. 快速排序演算法

快速排序（Quicksort）是對冒泡排序的一種改進。

然後，左邊和右邊的數據可以獨立排序。對於左側的數組數據，又可以取一個分界值，將該部分數據分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側的數組數據也可以做類似處理。

重復上述過程，可以看出，這是一個遞歸定義。通過遞歸將左側部分排好序後，再遞歸排好右側部分的順序。當左、右兩個部分各數據排序完成後，整個數組的排序也就完成了。

快速排序演算法通過多次比較和交換來實現排序，其排序流程如下：

(1)首先設定一個分界值，通過該分界值將數組分成左右兩部分。

(2)將大於或等於分界值的數據集中到數組右邊，小於分界值的數據集中到數組的左邊。此時，左邊部分中各元素都小於或等於分界值，而右邊部分中各元素都大於或等於分界值。

4. 快速排序演算法的排序演示

假設用戶輸入了如下數組： 下標 0 1 2 3 4 5 數據 6 2 7 3 8 9 創建變數i=0（指向第一個數據）, j=5(指向最後一個數據), k=6(賦值為第一個數據的值)。
我們要把所有比k小的數移動到k的左面，所以我們可以開始尋找比6小的數，從j開始，從右往左找，不斷遞減變數j的值，我們找到第一個下標3的數據比6小，於是把數據3移到下標0的位置，把下標0的數據6移到下標3，完成第一次比較： 下標 0 1 2 34 5 數據 3 2 7 6 8 9 i=0 j=3 k=6
接著，開始第二次比較，這次要變成找比k大的了，而且要從前往後找了。遞加變數i，發現下標2的數據是第一個比k大的，於是用下標2的數據7和j指向的下標3的數據的6做交換，數據狀態變成下表： 下標 0 1 2 3 4 5 數據 3 2 6 7 8 9 i=2 j=3 k=6
稱上面兩次比較為一個循環。
接著，再遞減變數j，不斷重復進行上面的循環比較。
在本例中，我們進行一次循環，就發現i和j「碰頭」了：他們都指向了下標2。於是，第一遍比較結束。得到結果如下，凡是k(=6)左邊的數都比它小，凡是k右邊的數都比它大： 下標 0 1 2 3 4 5 數據 3 2 6 7 8 9 如果i和j沒有碰頭的話，就遞加i找大的，還沒有，就再遞減j找小的，如此反復，不斷循環。注意判斷和尋找是同時進行的。
然後，對k兩邊的數據，再分組分別進行上述的過程，直到不能再分組為止。
注意：第一遍快速排序不會直接得到最終結果，只會把比k大和比k小的數分到k的兩邊。為了得到最後結果，需要再次對下標2兩邊的數組分別執行此步驟，然後再分解數組，直到數組不能再分解為止（只有一個數據），才能得到正確結果。 在c++中可以用函數qsort（）可以直接為數組進行排序。
用 法:
void qsort(void *base, int nelem, int width, int (*fcmp)(const void *,const void *));
參數：1 待排序數組首地址2 數組中待排序元素數量3 各元素的佔用空間大小4 指向函數的指針，用於確定排序的順序

5. C++數組排序有哪幾種演算法

插入排序演算法
1.從有序數列和無序數列{a2,a3,…,an}開始進行排序；
2.處理第i個元素時(i=2,3,…,n) , 數列{a1,a2,…,ai-1}是已有序的,而數列{ai,ai+1,…,an}是無序的。用ai與ai-1，a i-2,…,a1進行比較,找出合適的位置將ai插入；
3.重復第二步，共進行n-1次插入處理，數列全部有序。
void insertSort(Type* arr,long len)/*InsertSort algorithm*/
{
long i=0,j=0;/*iterator value*/
Type tmpData;
assertF(arr!=NULL,"In InsertSort sort,arr is NULL\n");
for(i=1;i<len;i++)
{
j=i;
tmpData=*(arr + i);
while(j > 0 && tmpData < arr[j-1])
{
arr[j]=arr[j-1];
j--;
}
arr[j]=tmpData;
}
}

歸並排序 ：歸並排序是多次將兩個或兩個以上的有序表合並成一個新的有序表。最簡單的歸並是直接將兩個有序的子表合並成一個有序的表。
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h >
void merge(int array[], int p, int q, int r)
{
int* temp = new int [r-p+1]; //申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合並後的序列
int m=p;
int n=q+1;
int k = 0;
while((m<=q)&&( n<=r)) //比較兩個下標所指向的元素，選擇相對小的元素放入到合並空間，並移動下標到下一位置
{
if(array[m]<array[n])
{
temp[k] = array[m];
m++;
}
else
{
temp[k] = array[n];
n++;
}
k++;
}
while(m<=q) //若第一個序列有剩餘，直接拷貝出來粘到合並序列尾
{
temp[k] = array[m];
k++;
m++;
}
while(n<=r) //若第二個序列有剩餘，直接拷貝出來粘到合並序列尾
{
temp[k] = array[n];
k++;
n++;
}
for (int i = 0; i < (r - p +1); i++) //將排序好的序列拷貝回數組中
{
array[p+i] = temp[i];
}
}
void mergesort(int A[],int p,int r)
{
if (p<r)
{
int q = (p+r)/2;
mergesort(A,p,q);
mergesort(A,q+1,r);
merge(A,p,q,r);
}
}
int main()
{
int A[9]={9,3,6,1,4,7,2,8,5};
mergesort(A,0,8);
for (int i = 0; i < 9; i++) //列印數組
{
cout<<A[i] ;
}
return 1;
}
C# 實現歸並排序
方法基本與樓上相同
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace LearnSort
{
class Program
{
static void Main(string[] args)
{
int[] arr = { 5, 4, 6, 7, 3, 5, 6, 1 };
Print(MergeSort(arr1));
}
public static int[] MergeSort(int[] arr)
{
MergeSort(arr, 0, arr.Length - 1);
return arr;
}
private static void MergeSort(int[] arr, int iStart, int iEnd)
{
if (iStart < iEnd)
{
int iMiddle = (iStart + iEnd) / 2;
MergeSort(arr, iStart, iMiddle);
MergeSort(arr, iMiddle + 1, iEnd);
MergeSort(arr, iStart, iMiddle, iEnd);
}
}
private static void MergeSort(int[] arr, int iStart, int iMiddle, int iEnd)
{
int[] temp = new int[iEnd - iStart + 1];
int m = iStart;
int n = iMiddle + 1;
int k = 0;
while (m <= iMiddle && n <= iEnd)
{
if (arr[m] < arr[n])
{
temp[k] = arr[m];
k++;
m++;
}
else
{
temp[k] = arr[n];
k++;
n++;
}
}
while (m <= iMiddle)
{
temp[k] = arr[m];
k++;
m++;
}
while (n <= iEnd)
{
temp[k] = arr[n];
k++;
n++;
}
for (k = 0, m = iStart; k < temp.Length; k++, m++)
{
arr[m] = temp[k];
}
}
public static void Print(int[] arr)
{
foreach (int i in arr)
{
System.Console.Write(i + " ");
}
System.Console.WriteLine();
}
}
}
冒泡排序：
#include <iostream>
#define LEN 9
using namespace std;
int main(){
int nArray[LEN];
for(int i=0;i<LEN;i++)nArray[i]=LEN-i;
cout<<"原始數據為："<<endl;
for(int i=0;i<LEN;i++)cout<<nArray[i]<<" ";
cout<<endl;
//開始冒泡
{
int temp;
for(int i=LEN-1;i>0;i--)
for(int j=0;j<i;j++){
if(nArray[j]>nArray[j+1]){
temp=nArray[j];
nArray[j]=nArray[j+1];
nArray[j+1]=temp;
}
}
}
//結束冒泡
cout<<"排序結果:"<<endl;
for(int i=0;i<LEN;i++)cout<<nArray[i]<<" ";
return 0;
}

快速排序：快速排序（Quicksort）是對冒泡排序的一種改進。由C. A. R. Hoare在1962年提出。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
源代碼
#include<iostream>
using namespace std;
void QuickSort(int *pData,int left,int right)
{
int i(left),j(right),middle(0),iTemp(0);
//middle=pData[(left+right)/2];求中間值
middle=pData[(rand()%(right-left+1))+left]; //生成大於等於left小於等於right的隨機數
do{
while((pData[i]<middle)&&(i<right))//從左掃描大於中值的數
i++;
while((pData[j]>middle) && (j>left))//從右掃描小於中值的數
j--;
//找到了一對值,交換
if(i<=j){
iTemp=pData[j];
pData[j]=pData[i];
pData[i]=iTemp;
i++;
j--;
}
}while(i<=j);//如果兩邊掃描的下標交錯，就停止（完成一次）
//當左邊部分有值(left<j)，遞歸左半邊
if(left<j){
QuickSort(pData,left,j);
}
//當右邊部分有值(right>i)，遞歸右半邊
if(right>i){
QuickSort(pData,i,right);
}
}
int main()
{
int data[]={10,9,8,7,6,5,4};
const int count(6);
QuickSort(data,0,count);
for(int i(0);i!=7;++i){
cout<<data[i]<<「 」<<flush;
}
cout<<endl;
return 0;
}

「堆」定義

n個關鍵字序列Kl，K2，…，Kn稱為(Heap)，當且僅當該序列滿足如下性質(簡稱為堆性質)：
(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ n)
若將此序列所存儲的向量R[1..n]看做是一棵完全二叉樹的存儲結構，則堆實質上是滿足如下性質的完全二叉樹：樹中任一非葉結點的關鍵字均不大於(或不小於)其左右孩子(若存在)結點的關鍵字。 （即如果按照線性存儲該樹，可得到一個不下降序列或不上升序列）
【例】關鍵字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分別滿足堆性質(1)和(2)，故它們均是堆，其對應的完全二叉樹分別如小根堆示例和大根堆示例所示。
大根堆和小根堆：根結點(亦稱為堆頂)的關鍵字是堆里所有結點關鍵字中最小者的堆稱為小根堆，又稱最小堆。根結點(亦稱為堆頂)的關鍵字是堆里所有結點關鍵字中最大者，稱為大根堆，又稱最大堆。注意：①堆中任一子樹亦是堆。②以上討論的堆實際上是二叉堆(Binary Heap)，類似地可定義k叉堆。

堆排序

堆排序利用了大根堆(或小根堆)堆頂記錄的關鍵字最大(或最小)這一特徵，使得在當前無序區中選取最大(或最小)關鍵字的記錄變得簡單。
（1）用大根堆排序的基本思想
① 先將初始文件R[1..n]建成一個大根堆,此堆為初始的無序區
② 再將關鍵字最大的記錄R[1](即堆頂)和無序區的最後一個記錄R[n]交換，由此得到新的無序區R[1..n-1]和有序區R[n]，且滿足R[1..n-1].keys≤R[n].key
③由於交換後新的根R[1]可能違反堆性質，故應將當前無序區R[1..n-1]調整為堆。然後再次將R[1..n-1]中關鍵字最大的記錄R[1]和該區間的最後一個記錄R[n-1]交換，由此得到新的無序區R[1..n-2]和有序區R[n-1..n]，且仍滿足關系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調整為堆。
……
直到無序區只有一個元素為止。
（2）大根堆排序演算法的基本操作：
① 初始化操作：將R[1..n]構造為初始堆；
② 每一趟排序的基本操作：將當前無序區的堆頂記錄R[1]和該區間的最後一個記錄交換，然後將新的無序區調整為堆(亦稱重建堆)。
注意：
①只需做n-1趟排序，選出較大的n-1個關鍵字即可以使得文件遞增有序。
②用小根堆排序與利用大根堆類似，只不過其排序結果是遞減有序的。堆排序和直接選擇排序相反：在任何時刻堆排序中無序區總是在有序區之前，且有序區是在原向量的尾部由後往前逐步擴大至整個向量為止
特點

堆排序(HeapSort)是一樹形選擇排序。堆排序的特點是：在排序過程中，將R[l..n]看成是一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系(參見二叉樹的順序存儲結構)，在當前無序區中選擇關鍵字最大(或最小)的記錄

堆排序與直接選擇排序的區別

直接選擇排序中，為了從R[1..n]中選出關鍵字最小的記錄，必須進行n-1次比較，然後在R[2..n]中選出關鍵字最小的記錄，又需要做n-2次比較。事實上，後面的n-2次比較中，有許多比較可能在前面的n-1次比較中已經做過，但由於前一趟排序時未保留這些比較結果，所以後一趟排序時又重復執行了這些比較操作。
堆排序可通過樹形結構保存部分比較結果，可減少比較次數。

演算法分析

堆[排序的時間，主要由建立初始]堆和反復重建堆這兩部分的時間開銷構成，它們均是通過調用Heapify實現的。
堆排序的最壞時間復雜度為O(nlog2n)。堆序的平均性能較接近於最壞性能。
由於建初始堆所需的比較次數較多，所以堆排序不適宜於記錄數較少的文件。
堆排序是就地排序，輔助空間為O(1)，
它是不穩定的排序方法。
[編輯本段]演算法描述

堆排序演算法(C++描述)

void HeapSort(SeqIAst R)
{ //對R[1..n]進行堆排序，不妨用R[0]做暫存單元
int i；
BuildHeap(R)； //將R[1-n]建成初始堆
for(i=n;i>1;i--)
{
//對當前無序區R[1..i]進行堆排序，共做n-1趟。
R[0]=R[1];
R[1]=R[i];
R[i]=R[0];//將堆頂和堆中最後一個記錄交換
Heapify(R，1，i-1)；
//將R[1..i-1]重新調整為堆，僅有R[1] 可能違反堆性質
} //endfor
}
//HeapSort
因為構造初始堆必須使用到調整堆的操作，先討論Heapify的實現，再討論如何構造初始堆(即BuildHeap的實現)
ps：一般的數組用冒泡就好了。

6. 數據結構 折中查找演算法/選擇排序 起泡排序演算法

折半查找法也稱為二分查找法，它充分利用了元素間的次序關系，採用分治策略，可在最壞的情況下用O(log n)完成搜索任務。它的基本思想是，將n個元素分成個數大致相同的兩半，取a[n/2]與欲查找的x作比較，如果x=a[n/2]則找到x，演算法終止。如果x<a[n/2]，則我們只要在數組a的左半部繼續搜索x（這里假設數組元素呈升序排列）。如果x>a[n/2]，則我們只要在數組a的右半部繼續搜索x。二分搜索法的應用極其廣泛，而且它的思想易於理解，但是要寫一個正確的二分搜索演算法也不是一件簡單的事。第一個二分搜索演算法早在1946年就出現了，但是第一個完全正確的二分搜索演算法直到1962年才出現。Bentley在他的著作《Writing Correct Programs》中寫道，90%的計算機專家不能在2小時內寫出完全正確的二分搜索演算法。問題的關鍵在於准確地制定各次查找范圍的邊界以及終止條件的確定，正確地歸納奇偶數的各種情況，其實整理後可以發現它的具體演算法是很直觀的，我們可用C++描述如下：

template<class Type>

int BinarySearch(Type a[],const Type& x,int n)

{

int left=0;

int right=n-1;

while(left<=right){

int middle=(left+right)/2;

if (x==a[middle]) return middle;

if (x>a[middle]) left=middle+1;

else right=middle-1;

}

return -1;

}

模板函數BinarySearch在a[0]<=a[1]<=...<=a[n-1]共n個升序排列的元素中搜索x,找到x時返回其在數組中的位置，否則返回-1。容易看出，每執行一次while循環，待搜索數組的大小減少一半,因此整個演算法在最壞情況下的時間復雜度為O(log n)。在數據量很大的時候，它的線性查找在時間復雜度上的優劣一目瞭然。
選擇排序
基本思想是：每次選出第i小的記錄，放在第i個位置（i的起點是0，按此說法，第0小的記錄實際上就是最小的，有點別扭，不管這么多了）。當i＝N－1時就排完了。

直接選擇排序
直選排序簡單的再現了選擇排序的基本思想，第一次尋找最小元素的代價是O(n)，如果不做某種特殊處理，每次都使用最簡單的尋找方法，自然的整個排序的時間復雜度就是O(n2)了。

冒泡法
為了在a[1]中得到最大值，我們將a[1]與它後面的元素a[2]，a[3]，...，a[10]進行比較。首先比較a[1]與a[2]，如果a[1]<a[2]，則將a[1]與a[2]交換，否則不交換。這樣在a[1]中得到的是a[1]與a[2]中的大數。然後將a[1]與a[3]比較，如果a[1]<a[3]，則將a[1]與a[3]交換，否則不交換。這樣在a[1]中得到的是a[1]，a[2]，a[3]中的最大值，...。如此繼續，最後a[1]與a[10]比較，如果a[1]<a[10]，則將a[1]與a[10]交換，否則不交換。這樣在a[1]中得到的數就是數組a的最大值（一共進行了9次比較）。

為了在a[2]中得到次大值，應將a[2]與它後面的元素a[3]，a[4]，...，a[10]進行比較。這樣經過8次比較，在a[2]是將得到次大值。

如此繼續，直到最後a[9]與a[10]比較，將大數放於a[9]，小數放於a[10]，全部排序到此結束。
從上面可以看出，對於10個數，需進行9趟比較，每一趟的比較次數是不一樣的。第一趟需比較9次，第二趟比較8次，...，最後一趟比較1次。

以上數組元素的排序，用二重循環實現，外循環變數設為i，內循環變數設為j。外循環重復9次，內循環依次重復9，8，...，1次。每次進行比較的兩個元素，第一個元素與外循環i有關的，用a[i]標識，第二個元素是與內循環j有關的，用a[j]標識，i的值依次為1,2,...,9，對於每一個i, j的值依次為i+1,i+2,...。

7. 如何用數組和選擇法將一組數(個數不定)從小到大排序

可以用Qsort，其中的qsort函數包含在<stdlib.h>的頭文件里，strcmp包含在<string.h>的頭文件里
七種qsort排序方法

<本文中排序都是採用的從小到大排序>

一、對int類型數組排序

int num[100];

Sample:

int cmp ( const void *a , const void *b )
{
return *(int *)a - *(int *)b;
}

qsort(num,100,sizeof(num[0]),cmp);

二、對char類型數組排序（同int類型）

char word[100];

Sample:

int cmp( const void *a , const void *b )
{
return *(char *)a - *(int *)b;
}

qsort(word,100,sizeof(word[0]),cmp);

三、對double類型數組排序（特別要注意）

double in[100];

int cmp( const void *a , const void *b )
{
return *(double *)a > *(double *)b ? 1 : -1;
}

qsort(in,100,sizeof(in[0]),cmp)；

四、對結構體一級排序

struct In
{
double data;
int other;
}s[100]

//按照data的值從小到大將結構體排序,關於結構體內的排序關鍵數據data的類型可以很多種，參考上面的例子寫

int cmp( const void *a ,const void *b)
{
return (*(In *)a).data > (*(In *)b).data ? 1 : -1;
}

qsort(s,100,sizeof(s[0]),cmp);

五、對結構體二級排序

struct In
{
int x;
int y;
}s[100];

//按照x從小到大排序，當x相等時按照y從大到小排序

int cmp( const void *a , const void *b )
{
struct In *c = (In *)a;
struct In *d = (In *)b;
if(c->x != d->x) return c->x - d->x;
else return d->y - c->y;
}

qsort(s,100,sizeof(s[0]),cmp);

六、對字元串進行排序

struct In
{
int data;
char str[100];
}s[100];

//按照結構體中字元串str的字典順序排序

int cmp ( const void *a , const void *b )
{
return strcmp( (*(In *)a)->str , (*(In *)b)->str );
}

qsort(s,100,sizeof(s[0]),cmp);

七、計算幾何中求凸包的cmp

int cmp(const void *a,const void *b) //重點cmp函數，把除了1點外的所有點，旋轉角度排序
{
struct point *c=(point *)a;
struct point *d=(point *)b;
if( calc(*c,*d,p[1]) < 0) return 1;
else if( !calc(*c,*d,p[1]) && dis(c->x,c->y,p[1].x,p[1].y) < dis(d->x,d->y,p[1].x,p[1].y)) //如果在一條直線上，則把遠的放在前面
return 1;
else return -1;
}

8. 幫忙寫幾個排序演算法！

普通排序的就沒有給你弄了。其他的快速排序，堆排序，希爾排序都有，每一步的輸出排序情況
#include<stdio.h>
//////////////////////////////////////////////
//堆排
void shift(int a[] , int i , int m)
{
int k , t;
int s;
t = a[i]; k = 2 * i + 1;
while (k < m)
{
if ((k < m - 1) && (a[k] < a[k+1])) k ++;
if (t < a[k])
{
a[i] = a[k]; i = k; k = 2 * i + 1;
}
else break;
}
a[i] = t;
for(s=0;s<10;s++)
printf("%d ",a[s]);
printf("\n");

}

void heap(int a[] , int n) //a 為排序數組，n為數組大小（編號0-n-1）
{
int i , k;

for (i = n/2-1; i >= 0; i --) shift(a , i , n);
for (i = n-1; i >= 1; i --)
{
k = a[0]; a[0] = a[i]; a[i] = k;
shift(a , 0 , i);
}
}

////////////////////////////////////////////////
//快排
void quick(int a[] , int s , int t) //a為排序數組，s為起點0 , t為終點 n-1
{
int i , j , x , y;
int k;
i = s; j = t; x = a[(i+j)/2];
while (i <= j)
{
while (a[i] < x) i ++;
while (a[j] > x) j --;
if (i <= j)
{
y = a[i]; a[i] = a[j]; a[j] = y;
i ++; j --;
for(k=0;k<10;k++) //輸出
printf("%d ",a[k]);
printf("\n");
}
}
if (i < t) quick(a , i , t);
if (s < j) quick(a , s , j);
}
///////////////////////////////////////////////////
//希爾排序
void shellsort(int a[],int n)
{
int i,j,g;
int s;
int temp,k;
g=n/2;
while(g!=0)
{
for(i=g+1;i<=n;i++)
{
temp=a[i];
j=i-g;
while(j>0)
{
k=j+g;
if(a[j]<=a[k])
j=0;
else
{
temp=a[j];a[j]=a[k];a[k]=temp;
}
j=j-g;
for(s=0;s<10;s++)
printf("%d ",a[s]);
printf("\n");
}
}
g=g/2;
}
}

/////////////////////////////
main()
{
int a[10]={1,5,3,4,7,4,2,56,7,8};
printf("快排");
quick(a,0,9);
printf("\n\n堆排序");
heap(a,10);
printf("\n\n希爾排序");
shellsort(a,10);
}

9. 數組排序是什麼

是將一個雜亂無章的數組進行一個快速排序，可以先從一個數組中取一個中間值。

排序演算法，通過特定的演算法因式將一組或多組數據按照既定模式進行重新排序。這種新序列遵循著一定的規則，體現出一定的規律，對於排序，我要求其具有一定的穩定性，即當兩個相同的元素同時出現於某個序列之中，則經過一定的排序演算法之後，兩者在排序前後的相對位置不發生變化。

常見的排序演算法：

1、選擇排序，選擇排序的基本思想是，基於直接選擇排序和堆排序這兩種基本的簡單排序方法。首先從第1個位置開始對全部元素進行選擇，選出全部元素中最小的給該位置，再對第2個位置進行選擇，在剩餘元素中選擇最小的給該位置。

2、快速排序，通過一趟排序演算法把所需要排序的序列的元素分割成兩大塊，其中，一部分的元素都要小於或等於另外一部分的序列元素，然後仍根據該種方法對劃分後的這兩塊序列的元素分別再次實行快速排序演算法，排序實現的整個過程可以是遞歸的來進行調用。

3、插入排序，通過一次插入一個元素的方式按照原有排序方式增加元素。這種比較是從該有序序列的最末端開始執行，即要插入序列中的元素最先和有序序列中最大的元素比較，若其大於該最大元素，則可直接插入最大元素的後面即可，否則再向前一位比較查找直至找到應該插入的位置為止。