01 冒泡排序
//冒泡排序1：直接排序法
void bubble_sorted_01(ElementType arr[], int N) {
?? ?
?? ?for (int i = 0;i < N - 1;i++) {
?? ??? ?bool flag = false;
?? ??? ?for (int j = 0;j < N - 1 - i;j++) {
?? ??? ??? ?if (arr[j] > arr[j + 1]) {
?? ??? ??? ??? ?flag = true;
?? ??? ??? ??? ?swap(arr[j], arr[j + 1]);
?? ??? ??? ?}?? ?
?? ??? ?}
?? ??? ?if (!flag)
?? ??? ??? ?break;
?? ?}
}
①直接排序法：
? ? ? ? 设置一个flag=false，如果在for(j=...)里面一次交换顺序的操作也没有执行就表明后面的数据已经是有序的了，就不用再进行排序了，可以直接通过break来退出循环。
?for (int i = 0;i < N - 1;i++)?
?? ??? ?for (int j = 0;j < N - 1-i;j++)?
使用i来代表需要排序多少趟，使用j来指示当前的位置，使用N-1-i来代表需要比较多少次，这种算法是先把最后面的元素排好序，然后再排前面的元素。
//冒泡排序2：间接排序法
void bubble_sorted_02(ElementType arr[], int N) {
?? ?int i,j,k;
?? ?for (i = 0;i < N - 1;i++) { ?//确定从前往后第i个位置应该放谁
?? ??? ?k = i;
?? ??? ?for (j = i+1;j < N;j++) { ?//从下一个元素一直到结尾，找一个当前最小的元素
?? ??? ??? ?if (arr[k] > arr[j]) {
?? ??? ??? ??? ?k = j;
?? ??? ??? ?}
?? ??? ?}
?? ??? ?if (k != i) swap(arr[i], arr[k]);?? ?//判断是否需要交换位置
?? ?}
}
②间接排序法：
?for (i = 0;i < N - 1;i++)?
?? ??? ?for (j = i+1;j < N;j++)
这种算法是从前往后把顺序排好，使用i来代表当前需要排序的位置(寻找应当存放在第i个位置的元素)，j代表的是第i个位置后面的元素，从第i个位置后面一个元素开始，一直到最后一个元素，寻找到当前最小的元素放置在第i个位置上。
间接排序的好处是如果第i个元素本身就是第i个位置的最小元素就不需要进行交换操作了。
间接排序可以上来就定义好i,j,k以便后面进行使用。
02 插入排序
//插入排序
void insertion_sort(ElementType arr[], int N) {
?? ?int i, j;
?? ?for (i = 1;i < N;i++) {
?? ??? ?ElementType tmp = arr[i];
?? ??? ?for (j = i;j >=1 && tmp < arr[j - 1];j--)
?? ??? ??? ?arr[j] = arr[j - 1];
?? ??? ?arr[j] = tmp;
?? ?}
}
插入排序：
先把最后一个位置的元素保存起来，然后将这个tmp值依次和前面的元素进行比较，如果还是当前位置前面的元素较大的话，就使用前面的元素来覆盖当前位置的元素，本例中使用i来代表最后一个元素的位置，使用j来代表当前的位置，如果tmp已经比当前位置的前一个元素还要大了，就可以直接使用tmp来覆盖当前第j个位置的值，在这里你不用担心第j个位置的值会丢失，因为在此之前第j个位置的值已经备份好了一份放在了第j+1位置处。
03 原始希尔排序
//原始希尔排序
void shell_sort(ElementType A[], int N) {
?? ?int D, p, k; ?//D为步长，p用来表示每一组的最后一个元素的位置，k用来表示当前比较元素的位置，k-D表示前一个元素的位置
?? ?for (int D = N / 2;D >=1;D /= 2) {?? ?//增量从2/N开始递减至1
?? ??? ?for (int p = D;p < N;p++) {?? ? //从第一个增量的位置开始,每++一次相当于换另外一组
?? ??? ??? ?ElementType tmp = A[p];
?? ??? ??? ?//对每一组进行插入排序
?? ??? ??? ?for (;k >= D && tmp < A[k - D];k -= D) // k要大于边界值，而k>=D 在前，因为也许 A[k-D]已经越界?
?? ??? ??? ??? ?A[k] = A[k - D];
?? ??? ??? ?A[k] = tmp;
?? ??? ?}
?? ?}
}
两种改进后的希尔排序：
01 Hibbard增量序列哈希排序
// Hibbard增量序列希尔排序 （希伯德）
void Hibbard_shell_sort(ElementType A[], int N) {
int add[] = { 32767,16383,8191,4095,2047,1023,511,255,127,63,31,15,7,3,1,0 };
int i = 0;
for (int D = add[i];D > 0;D = add[++i]) {
for (int p = D;p < N;p++) {
long tmp = A[p];
int k = p;
for (;k >= D && tmp < A[k - D];k -= D) // j>=D 在前，因为也许 A[j-D]已经越界
A[k] = A[k - D];
A[k] = tmp;
}
}
}
02 Sedgewick增量序列哈希排序
// Sedgewick增量序列哈希排序 (塞奇威克)
void Sedgewick_shell_sort(ElementType A[], int N) {
int add[] = { 587521,260609,146305,64769,36289,16001,8929,3905,2161,929,505,209,109,41,19,5,1,0 };
int i = 0;
for (int D = add[i];D > 0;D = add[++i]) {
for (int p = D;p < N;p++) {
long tmp = A[p];
int k = p;
for (;k >= D && tmp < A[k - D];k -= D)
A[k] = A[k - D];
A[k] = tmp;
}
}
}
|