快速排序c語言代碼
0和N-1表示的是數組下標。快排每一趟排序的目的是使值比設定的key值小的數都排到數組前部分，大的都排到後部分；然後對這兩部分用新的關鍵值key分別重復上一步的操作；遞歸，直到數組有序。
其中關鍵值key=a[low]。
用題目給定的數組模擬第一趟排序如下：
下標0123456789
值91647824661232551
low=0high=9
part_element=a[low]=9
進入for循環
進入第一個while
part_element<51，於是high--,high=8;
part_element<25，high--,high=7;
part_element>3,不滿足，結束while
a[low]=a[0]=a[high]=a[7]=3,low++,low=1;
進入第二個while
part_element<16,不滿足，結束while
a[high]=a[7]=a[low]=a[1]=16,high--,high=6
for第一個循環結束，數組如下
316478246612162551
low=1,high=6
for第二個循環同上，結束時數組如下
344782476612162551
low=2,high=3
for第三個循環，第一個while中high--以後，low==high，直接break跳出for循環，此時
344782476612162551
low=2,high=2
結束for以後
a[high]=a[2]=part_element=9,得到
34982476612162551
split函數returnhigh=2
quicksort函數中middle=2;
下面兩句遞歸，仍然是調用split函數，對數組
0-2,3-9兩部分分別重復上述操作
最後直到數組數據有序
2. 隨機生成一組整數，利用快速排序思想，將其從小到大排好。(c語言代碼)
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#defineRANDOM(i)(rand()%i)//隨機的常量
#defineN10//設置數組長度
//分區操作
intPartition(intarray[],intleft,intright)
{
inti,j;
inttemp;
j=left-1;
for(i=left;i<=right;i++)
{
if(array[i]<=array[right])//以最後一個數組的值為基準
{
j++;
temp=array[j];
array[j]=array[i];
array[i]=temp;
}
}
returnj;
}
//迭代運算
voidQuikSort(intarray[],intleft,intright)
{
intpivot;
if(left<right)
{
pivot=Partition(array,left,right);
QuikSort(array,left,pivot-1);
QuikSort(array,pivot+1,right);
}
}
/*主函數*/
intmain()
{
inti=0;
inta[N];
srand((int)time(0));//設置隨機數種子
for(i=0;i<N;i++)//排序前
{
a[i]=RANDOM(100);//100以內的隨機數
printf("%d ",a[i]);//輸出隨機得到的數組
}
printf(" ");
QuikSort(a,0,N-1);
for(i=0;i<N;i++)//輸出排序後的數組
{
printf("%d ",a[i]);
}
printf(" ");
}
3. 用C語言編寫一個快速排序演算法 輸入10個數
1、「快速排序法」使用的是遞歸原理，下面一個例子來說明「快速排序法」的原理。首先給出一個數組{53，12，98，63，18，72，80，46， 32，21}，先找到第一個數--53，把它作為中間值，也就是說，要把53放在一個位置，使得它左邊的值比它小，右邊的值比它大。{21，12，32， 46，18，53，80，72，63，98}，這樣一個數組的排序就變成了兩個小數組的排序--53左邊的數組和53右邊的數組，而這兩個數組繼續用同樣的方式繼續下去，一直到順序完全正確。一般來說，冒泡法是程序員最先接觸的排序方法，它的優點是原理簡單，編程實現容易，但它的缺點就是速度太慢。
2、快速排序代碼：
#include<stdio.h>
voidquicksort(inta[],intleft,intright)
{
inti,j,temp;
i=left;
j=right;
temp=a[left];
if(left>right)
return;
while(i!=j)
{
while(a[j]>=temp&&j>i)
j--;
if(j>i)
a[i++]=a[j];
while(a[i]<=temp&&j>i)
i++;
if(j>i)
a[j--]=a[i];
}
a[i]=temp;
quicksort(a,left,i-1);
quicksort(a,i+1,right);
}
voidmain()
{
inta[]={53,12,98,63,18,72,80,46,32,21};
inti;
quicksort(a,0,9);
/*排好序的結果*/
for(i=0;i<10;i++)
printf("%4d ",a[i]);
}
4. C語言中快速排序法的原理及應用
「快速排序法」使用的是遞歸原理，下面我結合一個例子來說明「快速排序法」的原理。首先給出一個數組{53，12，98，63，18，72，80，46， 32，21}，先找到第一個數--53，把它作為中間值，也就是說，要把53放在一個位置，使得它左邊的值比它小，右邊的值比它大。{21，12，32， 46，18，53，80，72，63，98}，這樣一個數組的排序就變成了兩個小數組的排序--53左邊的數組和53右邊的數組，而這兩個數組繼續用同樣的方式繼續下去，一直到順序完全正確。
一般來說，冒泡法是程序員最先接觸的排序方法，它的優點是原理簡單，編程實現容易，但它的缺點就是--程序的大忌--速度太慢。
附上快速排序代碼：
#include<stdio.h>
voidquicksort(inta[],intleft,intright)
{
inti,j,temp;
i=left;
j=right;
temp=a[left];
if(left>right)
return;
while(i!=j)
{
while(a[j]>=temp&&j>i)
j--;
if(j>i)
a[i++]=a[j];
while(a[i]<=temp&&j>i)
i++;
if(j>i)
a[j--]=a[i];
}
a[i]=temp;
quicksort(a,left,i-1);
quicksort(a,i+1,right);
}
voidmain()
{
inta[]={53,12,98,63,18,72,80,46,32,21};
inti;
quicksort(a,0,9);
/*排好序的結果*/
for(i=0;i<10;i++)
printf("%4d ",a[i]);
}
5. 急求c語言寫的各種排序代碼
數據結構作業吧
1.簡單選擇排序
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20
#define N 8
typedef int KeyType;
typedef int InfoType; /* 定義其它數據項的類型 */
typedef struct
{
KeyType key; /* 關鍵字項 */
InfoType otherinfo; /* 其它數據項，具體類型在主程中定義 */
}RedType; /* 記錄類型 */
typedef struct
{
RedType r[MAXSIZE+1]; /* r[0]閑置或用作哨兵單元 */
int length; /* 順序表長度 */
}SqList; /* 順序表類型 */
int SelectMinKey(SqList L,int i)
{ /* 返回在L.r[i..L.length]中key最小的記錄的序號 */
KeyType min;
int j,k;
k=i; /* 設第i個為最小 */
min=L.r[i].key;
for(j=i+1;j<=L.length;j++)
if(L.r[j].key<min) /* 找到更小的 */
{
k=j;
min=L.r[j].key;
}
return k;
}
void SelectSort(SqList *L)
{ /* 對順序表L作簡單選擇排序。演算法10.9 */
int i,j;
RedType t;
for(i=1;i<(*L).length;++i)
{ /* 選擇第i小的記錄，並交換到位 */
j=SelectMinKey(*L,i); /* 在L.r[i..L.length]中選擇key最小的記錄 */
if(i!=j)
{ /* 與第i個記錄交換 */
t=(*L).r[i];
(*L).r[i]=(*L).r[j];
(*L).r[j]=t;
}
}
}
void print(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}
int main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};
SqList l;
int i;
for(i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前:\n");
print(l);
SelectSort(&l);
printf("排序後:\n");
print(l);
system("pause");
return 0;
}
2.冒泡排序
#include<stdio.h>
#include<stdlib.h>
#define N 8
void bubble_sort(int a[],int n)
{ /* 將a中整數序列重新排列成自小至大有序的整數序列(起泡排序) */
int i,j,t;
int change;
for(i=n-1,change=1;i>1&&change;--i)
{
change=0;
for(j=0;j<i;++j)
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
change=1;
}
}
}
void print(int r[],int n)
{
int i;
for(i=0;i<n;i++)
printf("%d ",r[i]);
printf("\n");
}
int main()
{
int d[N]={49,38,65,97,76,13,27,49};
printf("排序前:\n");
print(d,N);
bubble_sort(d,N);
printf("排序後:\n");
print(d,N);
system("pause");
return 0;
}
3.歸並排序
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
#define N 7
typedef int KeyType;
typedef int InfoType; /* 定義其它數據項的類型 */
typedef struct
{
KeyType key; /* 關鍵字項 */
InfoType otherinfo; /* 其它數據項，具體類型在主程中定義 */
}RedType; /* 記錄類型 */
typedef struct
{
RedType r[MAXSIZE+1]; /* r[0]閑置或用作哨兵單元 */
int length; /* 順序表長度 */
}SqList; /* 順序表類型 */
void Merge(RedType SR[],RedType TR[],int i,int m,int n)
{ /* 將有序的SR[i..m]和SR[m+1..n]歸並為有序的TR[i..n] 演算法10.12 */
int j,k,l;
for(j=m+1,k=i;i<=m&&j<=n;++k) /* 將SR中記錄由小到大地並入TR */
if LQ(SR[i].key,SR[j].key)
TR[k]=SR[i++];
else
TR[k]=SR[j++];
if(i<=m)
for(l=0;l<=m-i;l++)
TR[k+l]=SR[i+l]; /* 將剩餘的SR[i..m]復制到TR */
if(j<=n)
for(l=0;l<=n-j;l++)
TR[k+l]=SR[j+l]; /* 將剩餘的SR[j..n]復制到TR */
}
void MSort(RedType SR[],RedType TR1[],int s, int t)
{ /* 將SR[s..t]歸並排序為TR1[s..t]。演算法10.13 */
int m;
RedType TR2[MAXSIZE+1];
if(s==t)
TR1[s]=SR[s];
else
{
m=(s+t)/2; /* 將SR[s..t]平分為SR[s..m]和SR[m+1..t] */
MSort(SR,TR2,s,m); /* 遞歸地將SR[s..m]歸並為有序的TR2[s..m] */
MSort(SR,TR2,m+1,t); /* 遞歸地將SR[m+1..t]歸並為有序的TR2[m+1..t] */
Merge(TR2,TR1,s,m,t); /* 將TR2[s..m]和TR2[m+1..t]歸並到TR1[s..t] */
}
}
void MergeSort(SqList *L)
{ /* 對順序表L作歸並排序。演算法10.14 */
MSort((*L).r,(*L).r,1,(*L).length);
}
void print(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}
int main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7}};
SqList l;
int i;
for(i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前:\n");
print(l);
MergeSort(&l);
printf("排序後:\n");
print(l);
system("pause");
return 0;
}
4.快速排序:
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20
#define N 8
typedef int KeyType;
typedef int InfoType; /* 定義其它數據項的類型 */
typedef struct
{
KeyType key; /* 關鍵字項 */
InfoType otherinfo; /* 其它數據項，具體類型在主程中定義 */
}RedType; /* 記錄類型 */
typedef struct
{
RedType r[MAXSIZE+1]; /* r[0]閑置或用作哨兵單元 */
int length; /* 順序表長度 */
}SqList; /* 順序表類型 */
int Partition(SqList *L,int low,int high)
{ /* 交換順序表L中子表L.r[low..high]的記錄，使樞軸記錄到位， */
/* 並返回其所在位置，此時在它之前(後)的記錄均不大(小)於它。演算法10.6(a) */
RedType t;
KeyType pivotkey;
pivotkey=(*L).r[low].key; /* 用子表的第一個記錄作樞軸記錄 */
while(low<high)
{ /* 從表的兩端交替地向中間掃描 */
while(low<high&&(*L).r[high].key>=pivotkey)
--high;
t=(*L).r[low]; /* 將比樞軸記錄小的記錄交換到低端 */
(*L).r[low]=(*L).r[high];
(*L).r[high]=t;
while(low<high&&(*L).r[low].key<=pivotkey)
++low;
t=(*L).r[low]; /* 將比樞軸記錄大的記錄交換到高端 */
(*L).r[low]=(*L).r[high];
(*L).r[high]=t;
}
return low; /* 返回樞軸所在位置 */
}
void QSort(SqList *L,int low,int high)
{ /* 對順序表L中的子序列L.r[low..high]作快速排序。演算法10.7 */
int pivotloc;
if(low<high)
{ /* 長度大於1 */
pivotloc=Partition(L,low,high); /* 將L.r[low..high]一分為二 */
QSort(L,low,pivotloc-1); /* 對低子表遞歸排序，pivotloc是樞軸位置 */
QSort(L,pivotloc+1,high); /* 對高子表遞歸排序 */
}
}
void QuickSort(SqList *L)
{ /* 對順序表L作快速排序。演算法10.8 */
QSort(L,1,(*L).length);
}
void print(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}
int main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};
SqList l;
int i;
for(i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前:\n");
print(l);
QuickSort(&l);
printf("排序後:\n");
print(l);
system("pause");
return 0;
}
6. 求大神編寫一個從大到小快速排序C語言程序，注意是從大到小！急，在線等！
#include<stdio.h>
#include"stdlib.h"
#include"time.h"
#defineN10
intcomp(constvoid*a,constvoid*b){
return*(int*)b-*(int*)a;
}
intmain(intargc,char*argv[]){
inta[N],i;
srand((unsigned)time(NULL));
for(i=0;i<N;i++)
printf("%4d",a[i]=rand()%1000);
printf(" Sorted: ");
qsort(a,10,sizeof(int),comp);
for(i=0;i<10;printf("%4d",a[i++]));
printf(" ");
return0;
}
7. 快速排序c語言
這是子程序。
void quicksort(int r[],int s,int t,int n)
{
int low=s,high=t,m;
int tmp;
if(s<t)
{
tmp=r[s];
while(low!=high)
{
while(high>low && r[high].key>tmp.key)
high--;
r[low]=r[high];
while(low<high && r[low].key<tmp.key)
low++;
r[high]=r[low];
}
n++;
r[low]=tmp;
printf("第 %d 層快速排序結果為:",n);
for(m=s;m<=t;m++)
{
printf(" %d ",r[m].key);
}
printf("\n");
quicksort(r,s,low-1,n);
quicksort(r,low+1,t,n);
}
8. C語言快速排序代碼
#include <stdio.h>
int partions(int l[],int low,int high)
{
int prvotkey=l[low];
l[0]=l[low];
while (low<high)
{
while (low<high&&l[high]>=prvotkey)
--high;
l[low]=l[high];
while (low<high&&l[low]<=prvotkey)
++low;
l[high]=l[low];
}
l[low]=l[0];
return low;
}
void qsort(int l[],int low,int high)
{
int prvotloc;
if(low<high)
{
prvotloc=partions(l,low,high); //將第一次排序的結果作為樞軸
qsort(l,low,prvotloc-1); //遞歸調用排序 由low 到prvotloc-1
qsort(l,prvotloc+1,high); //遞歸調用排序 由 prvotloc+1到 high
}
}
void quicksort(int l[],int n)
{
qsort(l,1,n); //第一個作為樞軸 ，從第一個排到第n個
}
void main()
{
int a[11]={0,2,32,43,23,45,36,57,14,27,39};
for (int b=1;b<11;b++)
printf("%3d",a[b]);
printf("\n");
quicksort(a,11);
for(int c=1;c<11;c++)
printf("%3d",a[c]);
}
9. 用C語言編寫函數，要實現快速排序演算法或者冒泡法
冒泡法排序函數如下：
void bubble(int a[],int n)
{int i,j,t;
for(i=0;i<n-1;i++)/*共進行n-1輪*/
for(j=0;j<n-1-i;j++)/*每輪在前n-i個數中比較*/
if(a[j]>a[j+1]) /*若相鄰元素逆序*/
{t=a[j]; a[j]=a[j+1];a[j+1]=t;}/*就交換*/
}
void sort(int *a, int left, int right)
{
if(left >= right)/*如果左邊索引大於或者等於右邊的索引就代表已經整理完成一個組了*/
{
return ;
}
int i = left;
int j = right;
int key = a[left];
while(i < j) /*控制在當組內尋找一遍*/
{
while(i < j && key <= a[j])
/*而尋找結束的條件就是，1，找到一個小於或者大於key的數（大於或小於取決於你想升
序還是降序）2，沒有符合條件1的，並且i與j的大小沒有反轉*/
{
j--;/*向前尋找*/
}
a[i] = a[j];
/*找到一個這樣的數後就把它賦給前面的被拿走的i的值（如果第一次循環且key是
a[left]，那麼就是給key）*/
while(i < j && key >= a[i])
/*這是i在當組內向前尋找，同上，不過注意與key的大小關系停止循環和上面相反，
因為排序思想是把數往兩邊扔，所以左右兩邊的數大小與key的關系相反*/
{
i++;
}
a[j] = a[i];
}
a[i] = key;/*當在當組內找完一遍以後就把中間數key回歸*/
sort(a, left, i - 1);/*最後用同樣的方式對分出來的左邊的小組進行同上的做法*/
sort(a, i + 1, right);/*用同樣的方式對分出來的右邊的小組進行同上的做法*/
/*當然最後可能會出現很多分左右，直到每一組的i = j 為止*/
}
10. 用C語言編程實現快速排序演算法
給個快速排序你參考參考
/**********************快速排序****************************
基本思想：在待排序的n個記錄中任取一個記錄（通常取第一個記錄），
以該記錄為基準，將當前的無序區劃分為左右兩個較小的無
序子區，使左邊的記錄均小於基準值，右邊的記錄均大於或
等於基準值，基準值位於兩個無序區的中間位置（即該記錄
最終的排序位置）。之後，分別對兩個無序區進行上述的劃
分過程，直到無序區所有記錄都排序完畢。
*************************************************************/
/*************************************************************
函數名稱：staticvoidswap(int*a,int*b)
參數：int*a---整型指針
int*b---整型指針
功能：交換兩個整數的位置
返回值：無
說明：static關鍵字指明了該函數只能在本文件中使用
**************************************************************/
staticvoidswap(int*a,int*b)
{
inttemp=*a;
*a=*b;
*b=temp;
}
intquickSortNum=0;//快速排序演算法所需的趟數
/*************************************************************
函數名稱：staticintpartition(inta[],intlow,inthigh)
參數：inta[]---待排序的數據
intlow---無序區的下限值
inthigh---無序區的上限值
功能：完成一趟快速排序
返回值：基準值的最終排序位置
說明：static關鍵字指明了該函數只能在本文件中使用
**************************************************************/
staticintpartition(inta[],intlow,inthigh)
{
intprivotKey=a[low];//基準元素
while(low<high)
{//從表的兩端交替地向中間掃描
while(low<high&&a[high]>=privotKey)//找到第一個小於privotKey的值
high--;//從high所指位置向前搜索，至多到low+1位置
swap(&a[low],&a[high]);//將比基準元素小的交換到低端
while(low<high&&a[low]<=privotKey)//找到第一個大於privotKey的值
low++;//從low所指位置向後搜索，至多到high-1位置
swap(&a[low],&a[high]);//將比基準元素大的交換到高端
}
quickSortNum++;//快速排序趟數加1
returnlow;//返回基準值所在的位置
}
/*************************************************************
函數名稱：voidQuickSort(inta[],intlow,inthigh)
參數：inta[]---待排序的數據
intlow---無序區的下限值
inthigh---無序區的上限值
功能：完成快速排序演算法，並將排序完成的數據存放在數組a中
返回值：無
說明：使用遞歸方式完成
**************************************************************/
voidQuickSort(inta[],intlow,inthigh)
{
if(low<high)
{
intprivotLoc=partition(a,low,high);//將表一分為二
QuickSort(a,low,privotLoc-1);//遞歸對低子表遞歸排序
QuickSort(a,privotLoc+1,high);//遞歸對高子表遞歸排序
}
}