排序演算法嗎
❶ 幾種常見的排序演算法
for(i = 0; i < n; i++) for(j = 0; j < n - 1 - i; j++){if(arr[j] arr[j + 1]){arr[j] = arr[j] ^ arr[j+1]; arr[j+1] = arr[j] ^ arr[j+1]; arr[j] = arr[j] ^ arr[j+1];}}} 交換兩個數據，可以用用臨時變數，也可用以下的兩個方法a = a^b;b = a^b;a = a^b;或者 a = a + b;b = a - b;a = a - b;// 選擇排序 void SelectSort(int arr[], int n){int i, j;int min; for(i = 0; i < n - 1; i++){int index = 0; min = arr[i]; for(j = i + 1; j < n; j++) //找出 i+1 - n 無序區的最小者與arr[i]交換{if(arr[j] < min){min = arr[j];index = j;}}if(index != 0) //表明無序區有比arr[i]小的元素{arr[i] = arr[i]^arr[index]; arr[index] = arr[i]^arr[index]; arr[i] = arr[i]^arr[index];}}}感覺比冒泡法好多啦 //快速排序演算法
❷ 關於排序演算法
沒有必要這么寫，一般都不這么寫的。
以下的程序已經改寫，運行通過，運行截圖中上例是原來的程序，第二次運行是改進後的程序運行的結果：
#include <stdio.h>
#define N 80
void fun(char s[], int n)
{
int i, j;
char ch;
for (i=0; i<n-1; i++)
for (j=i+1; j<n; j++)
if (s[i] < s[j])
{
ch = s[j];
s[j]=s[i];
s[i] = ch;
}
}
main()
{
int i = 0, strlen = 0;
char str[N];
printf(" Input a string: ");
gets(str);
while (str[i] != ' ')
{
strlen++;
i++;
}
fun(str, strlen);
printf(" ********* display string ********* ");
puts(str);
}
在程序演算法不變的前提下，程序可以簡化為：
#include <stdio.h>
#include <string.h>/*使用庫函數*/
#define N 80
void fun(char s[])
{
int i, j,n;
char ch;
n=strlen(s);
for (i=0; i<n-1; i++)
for (j=i+1; j<n; j++)
if (s[i] < s[j])
{
ch = s[j];
s[j]=s[i];
s[i] = ch;
}
}
main()
{
int i = 0;
char str[N];
printf(" Input a string: ");
gets(str);
fun(str);
printf(" ********* display string ********* ");
puts(str);
}
❸ 排序演算法
找網路，搞懂這幾種方法的原理。自己動腦寫。不要總是要別人解決。
❹ 最好的排序演算法是什麼演算法呀
什麼是最好？最快算是最好嗎？
目前就所有的內部排序法中，公認的使用廣泛的，是快速排序法，平均時間為 kn*lnn ，其中n為待排序序列中記錄的個數，k為某個常數。
❺ 幾種常用的排序演算法比較
排序，從小大，0坐標的在下面，即排序後小的在下面，大的在上面。
1，冒泡Bubble：從第0個開始，一直往上，與相鄰的元素比較，如果下面的大，則交換。
Analysis：
Implementation：
void BubbleSort(int *pData, int iNum)
2，插入Insertion：與打撲克牌時整理牌很想像，假定第一張牌是有序的，從第二張牌開始，拿出這張牌來，往下比較，如果有比這張牌大的，則把它撥到上一個位置，直到找到比手上的這張更小的（或到頂了），
則把手上的這張牌插入到這張更小的牌的後面。
Analysis：
Implementation：
void InsertionSort(int *list, int length)
{
int i, j, temp;
for (i = 1; i < length; i++)
{
temp = list[i];
j = i - 1;
while ((j >= 0) && (list[j] > temp))
{
list[j+1] = list[j];
j--;
}
list[j+1] = temp;
}
}
3，選擇Selection：從所有元素中找到最小的放在0號位置，從其它元素（除了0號元素）中再找到最小的，放到1號位置，......。
Analysis：
Implementation：
void SelectionSort(int data[], int count)
{
int i, j, min, temp;
for (i = 0; i < count - 1; i++)
{
/* find the minimum */
min = i;
for (j = i+1; j < count; j++)
{
if (data[j] < data[min])
{
min = j;
}
}
/* swap data[i] and data[min] */
temp = data[i];
data[i] = data[min];
data[min] = temp;
}
}
4，快速Quick：先拿出中間的元素來（值保存到temp里），設置兩個索引（index or pointer），一個從0號位置開始往最大位置尋找比temp大的元素；一個從最大號位置開始往最小位置尋找比temp小的元素，找到了或到頂了，則將兩個索引所指向的元素
互換，如此一直尋找交換下去，直到兩個索引交叉了位置，這個時候，從0號位置到第二個索引的所有元素就都比temp小，從第一個索引到最大位置的所有元素就都比temp大，這樣就把所有元素分為了兩塊，然後採用前面的辦法分別排序這兩個部分。總的來
說，就是隨機找一個元素（通常是中間的元素），然後把小的放在它的左邊，大的放右邊，對左右兩邊的數據繼續採用同樣的辦法。只是為了節省空間，上面採用了左右交換的方法來達到目的。
Analysis：
Implementation：
void QuickSort(int *pData, int left, int right)
{
int i, j;
int middle, iTemp;
i = left;
j = right;
middle = pData[(left + right) / 2]; //求中間值
do
{
while ((pData[i] < middle) && (i < right)) //從左掃描大於中值的數
i++;
while ((pData[j] > middle) && (j > left)) //從右掃描小於中值的數
j--;
if (i <= j) //找到了一對值
{
//交換
iTemp = pData[i];
pData[i] = pData[j];
pData[j] = iTemp;
i++;
j--;
}
} while (i <= j); //如果兩邊掃描的下標交錯，就停止（完成一次）
//當左邊部分有值(left<j)，遞歸左半邊
if(left < j)
QuickSort(pData, left, j);
//當右邊部分有值(right>i)，遞歸右半邊
if(right > i)
QuickSort(pData, i, right);
}
5，希爾Shell：是對Insertion Sort的一種改進，在Insertion Sort中，從第2個位置開始取出數據，每次都是與前一個（step/gap==1）進行比較。Shell Sort修改為，在開始時採用較大的步長step，
從第step位置開始取數據，每次都與它的前step個位置上的數據進行比較（如果有8個數據，初始step==4，那麼pos(4)與pos(0)比較，pos(0)與pos(-4)，pos(5)與pos(1)，pos(1)與pos(-3)，
...... pos(7)與pos(3)，pos(3)與pos(-1)），然後逐漸地減小step，直到step==1。step==1時，排序過程與Insertion Sort一樣，但因為有前面的排序，這次排序將減少比較和交換的次數。
Shell Sort的時間復雜度與步長step的選擇有很大的關系。Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort，MergeSort，HeapSort慢很多。但是它相對比較簡單，它適合
於數據量在5000以下並且速度並不是特別重要的場合。它對於數據量較小的數列重復排序是非常好的。
Analysis：
Implementation：
template<typename RandomIter, typename Compare>
void ShellSort(RandomIter begin, RandomIter end, Compare cmp)
{
typedef typename std::iterator_traits<RandomIter>::value_type value_type;
typedef typename std::iterator_traits<RandomIter>::difference_type diff_t;
diff_t size = std::distance(begin, end);
diff_t step = size / 2;
while (step >= 1)
{
for (diff_t i = step; i < size; ++i)
{
value_type key = *(begin+i);
diff_t ins = i; // current position
while (ins >= step && cmp(key, *(begin+ins-step)))
{
*(begin+ins) = *(begin+ins-step);
ins -= step;
}
*(begin+ins) = key;
}
if(step == 2)
step = 1;
else
step = static_cast<diff_t>(step / 2.2);
}
}
template<typename RandomIter>
void ShellSort(RandomIter begin, RandomIter end)
{
typedef typename std::iterator_traits<RandomIter>::value_type value_type;
ShellSort(begin, end, std::less<value_type>());
}
6，歸並Merge：先將所有數據分割成單個的元素，這個時候單個元素都是有序的，然後前後相鄰的兩個兩兩有序地合並，合並後的這兩個數據再與後面的兩個合並後的數據再次合並，充分前面的過程直到所有的數據都合並到一塊。
通常在合並的時候需要分配新的內存。
Analysis：
Implementation：
void Merge(int array[], int low, int mid, int high)
{
int k;
int *temp = (int *) malloc((high-low+1) * sizeof(int)); //申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合並後的序列
int begin1 = low;
int end1 = mid;
int begin2 = mid + 1;
int end2 = high;
for (k = 0; begin1 <= end1 && begin2 <= end2; ++k) //比較兩個指針所指向的元素，選擇相對小的元素放入到合並空間，並移動指針到下一位置
{
if(array[begin1]<=array[begin2])
{
temp[k] = array[begin1++];
}
else
{
temp[k] = array[begin2++];
}
}
if(begin1 <= end1) //若第一個序列有剩餘，直接拷貝出來粘到合並序列尾
{
memcpy(temp+k, array+begin1, (end1-begin1+1)*sizeof(int));
}
if(begin2 <= end2) //若第二個序列有剩餘，直接拷貝出來粘到合並序列尾
{
memcpy(temp+k, array+begin2, (end2-begin2+1)*sizeof(int));
}
memcpy(array+low, temp, (high-low+1)*sizeof(int));//將排序好的序列拷貝回數組中
free(temp);
}
void MergeSort(int array[], 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);
}
}
❻ 排序演算法有多少種
排序(Sorting) 是計算機程序設計中的一種重要操作，它的功能是將一個數據元素（或記錄）的任意序列，重新排列成一個關鍵字有序的序列。
排序就是把集合中的元素按照一定的次序排序在一起。一般來說有升序排列和降序排列2種排序，在演算法中有8中基本排序：
(1)冒泡排序；
(2)選擇排序；
(3)插入排序；
(4)希爾排序；
(5)歸並排序；
(6)快速排序；
(7)基數排序；
(8)堆排序；
(9)計數排序；
(10)桶排序。
插入排序
插入排序演算法是基於某序列已經有序排列的情況下，通過一次插入一個元素的方式按照原有排序方式增加元素。這種比較是從該有序序列的最末端開始執行，即要插入序列中的元素最先和有序序列中最大的元素比較，若其大於該最大元素，則可直接插入最大元素的後面即可，否則再向前一位比較查找直至找到應該插入的位置為止。插入排序的基本思想是，每次將1個待排序的記錄按其關鍵字大小插入到前面已經排好序的子序列中，尋找最適當的位置，直至全部記錄插入完畢。執行過程中，若遇到和插入元素相等的位置，則將要插人的元素放在該相等元素的後面，因此插入該元素後並未改變原序列的前後順序。我們認為插入排序也是一種穩定的排序方法。插入排序分直接插入排序、折半插入排序和希爾排序3類。
冒泡排序
冒泡排序演算法是把較小的元素往前調或者把較大的元素往後調。這種方法主要是通過對相鄰兩個元素進行大小的比較，根據比較結果和演算法規則對該二元素的位置進行交換，這樣逐個依次進行比較和交換，就能達到排序目的。冒泡排序的基本思想是，首先將第1個和第2個記錄的關鍵字比較大小，如果是逆序的，就將這兩個記錄進行交換，再對第2個和第3個記錄的關鍵字進行比較，依次類推，重復進行上述計算，直至完成第(n一1)個和第n個記錄的關鍵字之間的比較，此後，再按照上述過程進行第2次、第3次排序，直至整個序列有序為止。排序過程中要特別注意的是，當相鄰兩個元素大小一致時，這一步操作就不需要交換位置，因此也說明冒泡排序是一種嚴格的穩定排序演算法，它不改變序列中相同元素之間的相對位置關系。
選擇排序
選擇排序演算法的基本思路是為每一個位置選擇當前最小的元素。選擇排序的基本思想是，基於直接選擇排序和堆排序這兩種基本的簡單排序方法。首先從第1個位置開始對全部元素進行選擇，選出全部元素中最小的給該位置，再對第2個位置進行選擇，在剩餘元素中選擇最小的給該位置即可；以此類推，重復進行「最小元素」的選擇，直至完成第(n-1)個位置的元素選擇，則第n個位置就只剩唯一的最大元素，此時不需再進行選擇。使用這種排序時，要注意其中一個不同於冒泡法的細節。舉例說明：序列58539．我們知道第一遍選擇第1個元素「5」會和元素「3」交換，那麼原序列中的兩個相同元素「5」之間的前後相對順序就發生了改變。因此，我們說選擇排序不是穩定的排序演算法，它在計算過程中會破壞穩定性。
快速排序
快速排序的基本思想是:通過一趟排序演算法把所需要排序的序列的元素分割成兩大塊，其中，一部分的元素都要小於或等於另外一部分的序列元素，然後仍根據該種方法對劃分後的這兩塊序列的元素分別再次實行快速排序演算法，排序實現的整個過程可以是遞歸的來進行調用，最終能夠實現將所需排序的無序序列元素變為一個有序的序列。
歸並排序
歸並排序演算法就是把序列遞歸劃分成為一個個短序列，以其中只有1個元素的直接序列或者只有2個元素的序列作為短序列的遞歸出口，再將全部有序的短序列按照一定的規則進行排序為長序列。歸並排序融合了分治策略，即將含有n個記錄的初始序列中的每個記錄均視為長度為1的子序列，再將這n個子序列兩兩合並得到n/2個長度為2(當凡為奇數時會出現長度為l的情況)的有序子序列；將上述步驟重復操作，直至得到1個長度為n的有序長序列。需要注意的是，在進行元素比較和交換時，若兩個元素大小相等則不必刻意交換位置，因此該演算法不會破壞序列的穩定性，即歸並排序也是穩定的排序演算法。
❼ 幾種排序演算法的比較
一、八大排序演算法的總體比較
4.3、堆的插入：
每次插入都是將新數據放在數組最後。可以發現從這個新數據的父結點到根結點必然為一個有序的數列，然後將這個新數據插入到這個有序數據中
（1）用大根堆排序的基本思想
先將初始數組建成一個大根堆，此對為初始的無序區；
再將最大的元素和無序區的最後一個記錄交換，由此得到新的無序區和有序區，且滿足<=的值；
由於交換後新的根可能違反堆性質，故將當前無序區調整為堆。然後再次將其中最大的元素和該區間的最後一個記錄交換，由此得到新的無序區和有序區，且仍滿足關系的值<=的值，同樣要將其調整為堆；
..........
直到無序區只有一個元素為止；
4.4：應用
尋找M個數中的前K個最小的數並保持有序；
時間復雜度：O(K)[創建K個元素最大堆的時間復雜度] +（M-K）*log(K)[對剩餘M-K個數據進行比較並每次對最大堆進行從新最大堆化]
5.希爾排序
（1）基本思想
先將整個待排序元素序列分割成若乾子序列（由相隔某個「增量」的元素組成的）分別進行直接插入排序，然後依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序（因為直接插入排序在元素基本有序的情況下，效率很高）；
（2）適用場景
比較在希爾排序中是最主要的操作，而不是交換。用已知最好的步長序列的希爾排序比直接插入排序要快，甚至在小數組中比快速排序和堆排序還快，但在涉及大量數據時希爾排序還是不如快排；
6.歸並排序
（1）基本思想
首先將初始序列的n個記錄看成是n個有序的子序列，每個子序列的長度為1，然後兩兩歸並，得到n/2個長度為2的有序子序列，在此基礎上，再對長度為2的有序子序列進行兩兩歸並，得到若干個長度為4的有序子序列，以此類推，直到得到一個長度為n的有序序列為止；
（2）適用場景
若n較大，並且要求排序穩定，則可以選擇歸並排序；
7.簡單選擇排序
（1）基本思想
第一趟：從第一個記錄開始，將後面n-1個記錄進行比較，找到其中最小的記錄和第一個記錄進行交換；
第二趟：從第二個記錄開始，將後面n-2個記錄進行比較，找到其中最小的記錄和第2個記錄進行交換；
...........
第i趟：從第i個記錄開始，將後面n-i個記錄進行比較，找到其中最小的記錄和第i個記錄進行交換；
以此類推，經過n-1趟比較，將n-1個記錄排到位，剩下一個最大記錄直接排在最後；
❽ 幾種常用排序演算法
/** * @author txin0814 E-mail:[email protected] * @version 1.0 * @date Apr 1, 2011 2:28:06 PM * @description 排序類的 基類 */ public abstract class BaseSorter { public abstract void sort(E[] array,int from,int len); public final void sort(E[] array){ sort(array,0,array.length); } protected final void swap(E[] array,int from,int to){ E temp = array[from]; array[from] = array[to]; array[to] = temp; } } /** * @author txin0814 E-mail:[email protected] * @version 1.0 * @date Apr 1, 2011 2:34:47 PM * @description 插入排序 該演算法在數據規模小的時候十分高效， * 該演算法每次插入第K+1到前K個有序數組中一個合適位置， * K從0開始到N-1,從而完成排序 */ public class InsertSorter extends BaseSorter{ //當SORT_TYPE為false時按降序排列 為TRUE時按升序排列 public static boolean SORT_TYPE = false; @Override public void sort(E[] array, int from, int len) { E tmp=null; for(int i=from+1;ifrom;j--){ if(SORT_TYPE){ if(tmp.compareTo(array[j-1])0){ array[j]=array[j-1]; }else break; } } array[j]=tmp; } /*for (E e : array) { System.out.println(e); }*/ } public static void main(String[] args) { Integer[] elem = {32, 43, 1, 3, 54, 4, 19}; InsertSorter insertsort = new InsertSorter(); //InsertSorter.SORT_TYPE = true; insertsort.sort(elem); for (Integer integer : elem) { System.out.println(integer); } } } /** * @author txin0814 E-mail:[email protected] * @version 1.0 * @date Apr 1, 2011 2:53:29 PM * @description 冒泡排序 演算法思想是每次從數組末端開始比較相鄰兩元素，把第i小的冒泡到數組的第i個位置。) */ public class BubbleSorter extends BaseSorter { //當SORT_TYPE為false時按降序排列 為TRUE時按升序排列 public static boolean SORT_TYPE = false; public final void bubble_down(E[] array, int from, int len) { for (int i = from; i < from + len; i++) { for (int j = from + len - 1; j > i; j--) { if (array[j].compareTo(array[j - 1]) > 0) { swap(array, j - 1, j); } } } } public final void bubble_up(E[] array, int from, int len) { for (int i = from + len - 1; i >= from; i--) { for (int j = from; j < i; j++) { if (array[j].compareTo(array[j + 1]) > 0) { swap(array, j + 1, j ); } } } } @Override public void sort(E[] array, int from, int len) { if (SORT_TYPE) { bubble_up(array, from, len); } else { bubble_down(array, from, len); } } public static void main(String[] args) { Integer[] elem = {32, 43, 1, 3, 54, 4, 19}; BubbleSorter bsort = new BubbleSorter(); //BubbleSorter.DWON = true; //bsort.sort(elem); //BubbleSorter.SORT_TYPE = true; bsort.sort(elem, 0, elem.length); for (Integer integer : elem) { System.out.println(integer); } } } /** * @author txin0814 E-mail:[email protected] * @version 1.0 * @date Apr 1, 2011 3:17:42 PM * @description 選擇排序 選擇排序相對於冒泡來說，它不是每次發現逆序都交換， * 而是在找到全局第i小的時候記下該元素位置，最後跟第i個元素交換，從而保證數組最終的有序。
❾ 各種排序演算法
有插入排序，堆排序，快速排序，基排序，計數排序，桶排序，我說不完的，，詳情參看《演算法導論》