數據結構排序c語言
❶ c語言數據結構中的幾種內部排序法，求解！高手速度來指導我。。
1.Shell排序（ShellSort）
Shell排序通過將數據分成不同的組，先對每一組進行排序，然後再對所有的元素進行一次插入排序，以減少數據交換和移動的次數。平均效率是O(nlogn)。其中分組的合理性會對演算法產生重要的影響。現在多用D.E.Knuth的分組方法。
Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort，MergeSort，HeapSort慢很多。但是它相對比較簡單，它適合於數據量在5000以下並且速度並不是特別重要的場合。它對於數據量較小的數列重復排序是非常好的。
2.快速排序（QuickSort）
快速排序是一個就地排序，分而治之，大規模遞歸的演算法。從本質上來說，它是歸並排序的就地版本。快速排序可以由下面四步組成。
（1） 如果不多於1個數據，直接返回。
（2） 一般選擇序列最左邊的值作為支點數據。
（3） 將序列分成2部分，一部分都大於支點數據，另外一部分都小於支點數據。
（4） 對兩邊利用遞歸排序數列。
快速排序比大部分排序演算法都要快。盡管我們可以在某些特殊的情況下寫出比快速排序快的演算法，但是就通常情況而言，沒有比它更快的了。快速排序是遞歸的，對於內存非常有限的機器來說，它不是一個好的選擇。
3堆排序（HeapSort）
堆排序適合於數據量非常大的場合（百萬數據）。
堆排序不需要大量的遞歸或者多維的暫存數組。這對於數據量非常巨大的序列是合適的。比如超過數百萬條記錄，因為快速排序，歸並排序都使用遞歸來設計演算法，在數據量非常大的時候，可能會發生堆棧溢出錯誤。
堆排序會將所有的數據建成一個堆，最大的數據在堆頂，然後將堆頂數據和序列的最後一個數據交換。接下來再次重建堆，交換數據，依次下去，就可以排序所有的數據。
下面是一個總的表格（這張表很重要），大致總結了我們常見的所有的排序演算法的特點。
排序法 平均時間 最差情形 穩定度 額外空間 備注
冒泡 O(n2) O(n2) 穩定 O(1) n小時較好
交換 O(n2) O(n2) 不穩定 O(1) n小時較好
選擇 O(n2) O(n2) 不穩定 O(1) n小時較好
插入 O(n2) O(n2) 穩定 O(1) 大部分已排序時較好
基數 O(logRB) O(logRB) 穩定 O(n)
B是真數(0-9)，
R是基數(個十百)
Shell O(nlogn) O(ns) 1<s<2 不穩定 O(1) s是所選分組
快速 O(nlogn) O(n2) 不穩定 O(nlogn) n大時較好
歸並 O(nlogn) O(nlogn) 穩定 O(1) n大時較好
堆 O(nlogn) O(nlogn) 不穩定 O(1) n大時較好
備注:O(n2)表示雙重循環，即n^2
❷ 數據結構C語言--三種以上的排序演算法
快速排序：
void QSort(int a[], int l, int r) //單關鍵字交換法快排
{
int i = l, j = r, mid = (i + j) / 2; //二分[i,j]區間
while (i <= j) //讓a[mid]左邊都比a[mid]小，右邊都比a[mid]大
{
while (a[i] < a[mid]) //找到一個元素a[i]比a[mid]小
i++;
while (a[j] > a[mid]) //找到一個元素a[j]比a[mid]大
j--;
if (i <= j) //交換a[i]和a[j]，並讓指針向中間靠攏
Swap(a[i++], a[j--]);
}
if (i < r)
QSort(a, i, r); //對右區間[i,r]遞歸排序
if (l < j)
QSort(a, l, j); //對左區間[l,j]遞歸排序
}
歸並排序：
void Merge(int a[], int l, int m, int r) //將a中區間[l, r]合並為有序
{
int x[101], y[101]; //循環變數
int i, j, k;
int l1 = m - l + 1, l2 = r - m; //l1表示區間[l, m]的長度，l2表示區間[m + 1, r]的長度
for (i = 1; i <= l1; i++) //將a中區間[l, m]復制到x中
{
x[i] = a[l + i - 1];
}
for (i = 1; i <= l2; i++) //將a中區間[m + 1, r]復制到y中
{
y[i] = a[m + i];
}
x[l1 + 1] = MaxInt; //設置一個很大的數作為結束標志
y[l2 + 1] = MaxInt;
i = 1;
j = 1;
for (k = l; k <= r; k++) //將兩個區間合並成為一個有序區間
{
if (x[i] <= y[j])
{
a[k] = x[i++];
}
else
{
a[k] = y[j++];
}
}
}
void MergeSort(int a[], int l, int r) //對a數組的[l, r]區間排序
{
int m;
if (l < r)
{
m = (l + r) / 2; //二分區間[l, r]
MergeSort(a, l, m); //遞歸二分區間[l, m]
MergeSort(a, m + 1, r); //遞歸二分區間[m + 1, r]
Merge(a, l, m, r); //合並區間[l, m]和[m + 1, r]
}
}
二叉排序樹排序：
struct BinaryTree //二叉樹結構
{
int data, p, l, r; //data數值域，p父節點編號，l左兒子編號，r右兒子編號
};
int root = 0;
void Init(BinaryTree a[], int &n) //讀入數據域，並初始化樹
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i].data;
a[i].p = a[i].l = a[i].r = -1;
}
}
void Insert(BinaryTree a[], int i) //在二叉查找樹中插入編號為 i 的節點
{
int parent = -1, x = a[1].p; //parent 始終指向 x 的父節點編號
while (x != -1) //向下搜索，直到找到最下一層
{
parent = x;
if (a[i].data < a[x].data)
x = a[x].l;
else
x = a[x].r;
}
a[i].p = parent; //把第 i 號節點的父親指向parent
if (parent != -1) //判斷樹是否為空
{
if (a[i].data < a[parent].data) //向父節點插入兒子
a[parent].l = i;
else
a[parent].r = i;
}
else //為空就以 i 節點為根節點
a[root].p = i;
}
void BuildTree(BinaryTree a[], int n) //建立二叉查找樹
{
root = 1;
for (int i = 1; i <= n; i++) //依次插入 n 個節點到二叉查找樹
{
Insert(a, i);
}
a[root].p = -1;
}
void Sort(BinaryTree a[], int i) //中序遍歷輸出
{
if (a[i].l > -1) //遞歸遍歷左兒子
Sort(a, a[i].l);
cout << a[i].data << " "; //輸出節點
if (a[i].r > -1) //遞歸遍歷右兒子
Sort(a, a[i].r);
}
堆排序：
void Heap(int a[], int n, int p) //維護最大（最小）堆，維護以P為根的堆
{
int l = p * 2, r = l + 1, t = p; //左兒子編號為2P，右兒子為2P+1，初始化根節點P為最大
if ((l <= n) && (a[l] > a[p])) //找一個最大的數，維護最大堆（改為<就是維護最小堆）
t = l;
if ((r <= n) && (a[r] > a[t])) //找一個最大的數，維護最大堆（改為<就是維護最小堆）
t = r;
if (p != t) //如果根節點不是最大，和最大的交換，再遞歸維護堆
{
Swap(a[p], a[t]);
Heap(a, n, t);
}
}
void HeapSort(int a[], int n)
{
int i;
for (i = n / 2; i >= 1; i--) //n / 2開始必然是根節點，依次調用Heap，建立一個最大堆
Heap(a, n, i);
for (i = n; i >= 2; i--) //每次將堆頂和當前堆最後一個節點(i)交換，然後將[1, i - 1]重新堆化
{
Swap(a[i], a[1]);
Heap(a, i - 1, 1);
}
}
插入排序：
void InsertionSort(int a[], int l, int r) //對區間[l, r]執行插入排序
{
int i, j, t;
for (i = l + 1; i <= r; i++)
{
j = i - 1;
t = a[i];
while ((j >= l) && (a[j] > t)) //後移操作，並找到正確的位置
{
a[j + 1] = a[j];
j--;
}
a[j + 1] = t;
}
}
以上所有的Swap函數的意思都是交換兩個變數。
❸ 在數據結構中用c語言怎麼編寫用單鏈表將26個字母排序的程序
#include <stdio.h>
#include <stdlib.h>
//申明鏈表
typedef struct node
{
char num;
struct node *next;
}list;
void Bubble_sort(list *L);//鏈表的冒泡排序
void Dis_list(list *L);//遍歷單鏈表
int main()
{
//建表
list *r,*s,*p;
int n=26;//存儲數據的個數
s=NULL;
for(int i='Z';i>='A';i--)
{
r=(list *)malloc(sizeof(list));
r->num = i;
if(!s){s=r;p=s;}
p->next=r;
p=r;
}
p->next=NULL;
printf("排序前:\t");
Dis_list(s);
//排序
Bubble_sort(s);
printf("排序後:\t");
Dis_list(s);
return 0;
}
void Dis_list(list *L)
{
list *r;
r=L;
while(r!=NULL)
{
printf("%c\t",r->num);
r=r->next;
}
printf("\n");
}
void Bubble_sort(list *L)
{
list *r,*s;
char temp;
for(r=L;r;r=r->next)
{
for(s=r;s;s=s->next)
{
if(r->num>s->num)
{
temp=r->num;
r->num=s->num;
s->num=temp;
}
}
}
}
❹ C語言中結構體數據排序
設結構體名為AAA，結構體數組聲明為struct AAA a[N];(N為宏定義常量)，身份證成員名為id，則排序函數可如下寫——
#include"stdio.h"
#include<string.h>
#defineN3
structAAA{
charid[20];
intage;
};
voidmysort(structAAA*p){//排序函數
structAAAt;
inti,j,k;
for(i=0;i<N;i++){
for(k=i,j=k+1;j<N;j++)
if(strcmp((p+j)->id,(p+k)->id)<0)
k=j;
if(i!=k)
t=*(p+k),*(p+k)=*(p+i),*(p+i)=t;
}
}
intmain(intargc,char*argv[]){//測試主函數
structAAAa[N]={{"650104194812109907",77},{"333018201801015555",1},{"650104194812109903",80}};
mysort(a);
printf("%s %d ",a[0].id,a[0].age);
printf("%s %d ",a[1].id,a[1].age);
printf("%s %d ",a[2].id,a[2].age);
return0;
}
運行結果：
❺ 輸入一組整數對該序列進行簡單選擇和歸並排序（數據結構用c語言寫啊）
給你一個歸並排序的具體演算法和分析：
兩路歸並排序演算法思路:
①.
把n個記錄看成n個長度為l的有序子表
;
②.
進行兩兩歸並使記錄關鍵字有序,得到n/2個長度為2的有序子表;
③.
重復第②步直到所有記錄歸並成一個長度為n的有序表為止;
具體演算法:
//
歸並操作
template
static
void
merge
(typearray[],
int
p,
int
q,
int
r){
int
i
,
k
;
int
begin1
,
end1
,
begin2
,
end2
;
int*
temp
=
(int*)malloc((r-p)*sizeof(int))
;
begin1
=
p
;
end1
=
q
;
begin2
=
q+1
;
end2
=
r
;
k
=
0
;
while
(begin1
<=
end1
&&
begin2
<=
end2){
if
(array[begin1]
<
array[begin2]){
temp[k]
=
array[begin1]
;
begin1
++
;
}
else{
temp[k]
=
array[begin2]
;
begin2
++
;
}
k
++
;
}
while
(begin1
<
end1)
temp[k++]
=
array[begin1++]
;
while
(begin2
<
end2)
temp[k++]
=
array[begin2++]
;
for
(i
=
0
;
i
<
(r-p)
;
i
++)
array[p+i]
=
temp
;
free(temp)
;
}
//--------------------------------------------------------------------------------
template
void
mergesort(typearray[],
unsigned
int
first,
unsigned
int
last){
int
mid
=
0
;
if
(first
<
last)
{
mid
=
(first+last)/2
;
mergesort
(array,
first,
mid)
;
mergesort
(array,
mid+1,
last)
;
merge
(array,
first,
mid,
last)
;
}
}
❻ 數據結構(c語言)中快速排序什麼時候排序最慢，什麼情況下使用快速排序
當待排序的序列已經有序（不管是升序還是降序），此時快速排序最慢，一般當數據量很大的時候，用快速排序比較好，為了避免原來的序列有序，一般採用改進的快速排序演算法，在排序之前隨機交換兩個元素的位置，就可以達到目的了，有一本書，叫《演算法設計、分析與實現：C、C++和java》徐子珊著。可以看看，裡面寫了很多基本的演算法
❼ 數據結構C語言——實現各種排序演算法
剛做完的
#include <iostream>
using namespace std;
void BiInsertsort(int r[], int n) //插入排序（折半）
{
for(int i=2;i<=n;i++)
{
if (r[i]<r[i-1])
{
r[0] = r[i]; //設置哨兵
int low=1,high=i-1; //折半查找
while (low<=high)
{
int mid=(low+high)/2;
if (r[0]<r[mid]) high=mid-1;
else low = mid+1;
}
int j;
for (j=i-1;j>high;j--) r[j+1] = r[j]; //後移
r[j+1] = r[0];
}
}
for(int k=1;k<=n;k++) cout<<r[k]<<" ";
cout<<"\n";
}
void ShellSort ( int r[], int n) //希爾排序
{
for(int d=n/2;d>=1;d=d/2) //以d為增量進行直接插入排序
{
for (int i=d+1;i<=n;i++)
{
r[0] = r[i]; //暫存被插入記錄
int j;
for( j=i-d; j>0 && r[0]<r[j]; j=j-d) r[j+d] = r[j]; //記錄後移d個位置
r[j+d] = r[0];
}
}
for(int i=1;i<=n;i++) cout<<r[i]<<" ";
cout<<"\n";
}
void BubbleSort(int r[], int n) //起泡排序
{
int temp,exchange,bound;
exchange=n; //第一趟起泡排序的范圍是r[0]到r[n-1]
while (exchange) //僅當上一趟排序有記錄交換才進行本趟排序
{
bound=exchange;
exchange=0;
for (int j=1; j<bound; j++) //一趟起泡排序
if (r[j]>r[j+1])
{
temp=r[j];
r[j]=r[j+1];
r[j+1]=temp;
exchange=j; //記錄每一次發生記錄交換的位置
}
}
for(int i=1;i<=n;i++) cout<<r[i]<<" ";
cout<<"\n";
}
int Partition(int r[], int first, int end) //快速排序一次劃分
{
int i=first; //初始化
int j=end;
r[0]=r[first];
while (i<j)
{
while (i<j && r[0]<= r[j]) j--; //右側掃描
r[i]=r[j];
while (i<j && r[i]<= r[0]) i++; //左側掃描
r[j]=r[i];
}
r[i]=r[0];
return i; //i為軸值記錄的最終位置
}
void QuickSort(int r[], int first, int end) //快速排序
{
if (first<end)
{ //遞歸結束
int pivot=Partition(r, first, end); //一次劃分
QuickSort(r, first, pivot-1);//遞歸地對左側子序列進行快速排序
QuickSort(r, pivot+1, end); //遞歸地對右側子序列進行快速排序
}
}
void SelectSort(int r[ ], int n) //簡單選擇排序
{
int i,j,index,temp;
for (i=1; i<n; i++) //對n個記錄進行n-1趟簡單選擇排序
{
index=i;
for (j=i+1; j<=n; j++) //在無序區中選取最小記錄
if (r[j]<r[index]) index=j;
if (index!=i)
{
temp=r[i];
r[i]=r[index];
r[index]=temp;
}
}
for(i=1;i<=n;i++) cout<<r[i]<<" ";
cout<<"\n";
}
void main()
{
const int numv=12;
int a[3][numv]={{0,6,13,19,23,37,39,41,45,48,58,86},{0,86,58,48,45,41,39,37,23,19,13,6},{0,23,13,48,86,19,6,41,58,37,45,39}};
int z1[numv],z2[numv];
int m,n;
cout<<"請選擇測試數據類型：⑴正序 ⑵逆序 ⑶隨機 [ 若跳出,請按⑷ ]" <<endl;
cin>>m;
while(m>0&&m<4)
{
cout<<"請選擇排序演算法：⑴直接插入排序 ⑵希爾排序 ⑶冒泡排序 ⑷快速排序 \n ⑸簡單選擇排序"<<endl;
cin>>n;
switch(n)
{
case 1:
cout << "直接插入排序前：" << "\n";
for(int j=1;j<numv;j++) cout<<a[m-1][j]<<" ";
cout << "\n直接插入排序結果為：" << "\n";
BiInsertsort(a[m-1],numv-1);
break;
case 2:
cout << "\n希爾排序前：" << "\n";
for(int j=1;j<numv;j++) cout<<a[m-1][j]<<" ";
cout << "\n希爾排序結果為：" << "\n";
ShellSort(a[m-1], numv-1);
break;
case 3:
cout << "\n冒泡排序前：" << "\n";
for(int k=1;k<numv;k++) cout<<a[m-1][k]<<" ";
cout << "\n冒泡排序結果為：" << "\n";
BubbleSort(a[m-1], numv-1);
break;
case 4:
cout << "\n快速排序前：" << "\n";
for(int j=1;j<numv;j++) cout<<a[m-1][j]<<" ";
cout << "\n快速排序結果為：" << "\n";
QuickSort(a[m-1],0,numv-1);
for(int i=1;i<numv;i++)
cout<<a[m-1][i]<<" ";
cout<<"\n";
break;
case 5:
cout << "\n簡單選擇排序前：" << "\n";
for(int j=1;j<numv;j++) cout<<a[m-1][j]<<" ";
cout << "\n簡單選擇排序結果為：" << "\n";
SelectSort(a[m-1],numv-1);
break;
default:
cout<<"輸入錯誤！"<<endl;
}
m=0;
cout<<"請選擇測試數據類型：⑴正序 ⑵逆序 ⑶隨機 [ 若跳出,請按⑷ ]" <<endl;
cin>>m;
}
if(m==4) cout<<"(*^__^*) 再見！"<<endl;
else cout<<"輸入錯誤！"<<endl;
}
❽ c語言三種排序
常用的c語言排序演算法主要有三種即冒泡法排序、選擇法排序、插入法排序。
一、冒泡排序冒泡排序：
是從第一個數開始，依次往後比較，在滿足判斷條件下進行交換。代碼實現（以降序排序為例）
#include<stdio.h>
int main()
{
int array[10] = { 6,9,7,8,5,3,4,0,1,2 };
int temp;
for (int i = 0; i < 10; i++)
{//循環次數
for (int j = 0; j <10 - i-1; j++)
{
if (array[j] < array[j+1])
{//前面一個數比後面的數大時發生交換 temp = array[j];
array[j] = array[j+1];
array[j + 1] = temp;
}
}
} //列印數組 for (int i = 0; i < 10; i++) printf("%2d", array[i]); return 0;}}
二、選擇排序以升序排序為例：
就是在指定下標的數組元素往後（指定下標的元素往往是從第一個元素開始，然後依次往後），找出除指定下標元素外的值與指定元素進行對比，滿足條件就進行交換。與冒泡排序的區別可以理解為冒泡排序是相鄰的兩個值對比，而選擇排序是遍歷數組，找出數組元素與指定的數組元素進行對比。（以升序為例）
#include<stdio.h>
int main()
{
int array[10] = { 6,9,7,8,5,3,4,0,1,2 };
int temp, index;
for (int i = 0; i < 9; i++) {
index = i;
for (int j = i; j < 10; j++)
{
if (array[j] < array[index])
index = j;
}
if(i != index)
{
temp = array[i];
array[i] = array[index];
array[index] = temp;
}
for(int i=0;i<10:i++)
printf("%2d"array[i]）
return 0；
}
三、快速排序
是通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
void QuickSort(int* arr, int size)
{
int temp, i, j;
for(i = 1; i <size; i++)
for(j=i; j>0; j--)
{
if(arr[j] <arr[j-1])
{
temp = arr[j];
arr[j]=arr[j-1];
arr[j-1]=temp;
}
}
}