数据结构--排序_数据结构排序问题

冒泡

void bubble_sort(vector<int>& v){
     int size = v.size();
     int flag = 0;
     for (int i = 0; i < size-1;++i){
         for (int j = i + 1; j < size;++j){
              if (v[i]>v[j])
                  swap(v[i], v[j]);
         }
     }
}
1
2
3
4
5
6
7
8
9
10
11

冒泡排序优化

void bubble_sort(vector<int>& v){
     int size = v.size();
     int flag = 0;
     for (int i = 0; i < size-1;++i){
         for (int j = i + 1; j < size;++j){
              if (v[i]>v[j]){
                  flag = 1;
                  swap(v[i], v[j]);
              }
         }
         if (flag == 0)
              break;
     }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

选择排序

void select_sort(vector<int>& v){
     int min = 0;
     int max = v.size() - 1;
     for (int i = 0; i < v.size()-1;++i){
         min = i;
         for (int j = i + 1; j < v.size();++j){
              if (v[j] < v[min])
                  min = j;
         }
         if (min != i)
              swap(v[i], v[min]);
     }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

http://blog.csdn.net/qq_34312386/article/details/60573690

选择排序优化

void select_sort2(vector<int>& v){
     int min = 0;
     int max = v.size() - 1;
     int left = 0;
     int right = v.size() - 1;
     for (; left <= right;++left,--right){
         max = right;
         min = left;
         for (int i = left + 1; i <= right;++i){
              if (v[i] < v[min])
                  min = i;
              if (v[i] > v[max])
                  max = i;
         }
         if (max != right)
              swap(v[right], v[max]);
         if (min == right)
              min = max;
         swap(v[min], v[left]);
     }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

http://blog.csdn.net/qq_34312386/article/details/60573690

直接插入排序

void insert_sort(vector<int>& v){
     int pos = 0;
     for (int i = pos+1; i < v.size();++i){
         pos = i - 1;
         int ret = v[i];
         while (pos >= 0 && ret < v[pos]){
              v[pos + 1] = v[pos];
              --pos;
         }
         v[pos + 1] = ret;
     }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

http://blog.csdn.net/qq_34312386/article/details/60491169

希尔排序

void shell_sort(vector<int>& v){
     int gap = v.size();
     int pos = 0;
     while (gap>1){
         gap = gap / 2;
         for (int i = pos + gap;i<v.size();i+=gap){
              pos = i - gap;
              int ret = v[i];
              while (pos >= 0 && ret<v[pos]){

              }
         }
     }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

http://blog.csdn.net/qq_34312386/article/details/60491169

堆排

void AdjustDown(vector<int>& v,int left,int end){
     int parent = left;
     int child = left * 2 + 1;
     while (parent<end){
         if (child + 1 < end && v[child] < v[child + 1])
              ++child;
         if (child<end && v[child]>v[parent]){
              swap(v[child], v[parent]);
              parent = child;
              child = parent * 2 + 1;
         }
         else
              break;
     }
}
void heap_sort(vector<int>& v){
     int size = v.size();
     for (int i = (size - 2) / 2; i >= 0; --i)
         AdjustDown(v,i,size);

     for (int end = size - 1; end > 0;--end){
         swap(v[0], v[end]);
         AdjustDown(v, 0, end);
     }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

http://blog.csdn.net/qq_34312386/article/details/61416759

快速排序

前后指针法

int Partition(vector<int>& v, int left,int right){
     int key = v[right];
     int end = right;
     while (left<right){
         while (left < right && v[left] <= key)
              left++;
         while (left<right && v[right]>=key)
              right--;
         if (v[left]>v[right])
              swap(v[left], v[right]);
     }
     swap(v[left], v[end]);
     return left;
}
void QuickSort(vector<int>& v, int left, int right){
     if (left<right){
         int pivotpos = Partition(v, left, right);
         QuickSort(v, left, pivotpos - 1);
         QuickSort(v, pivotpos + 1, right);
     }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

挖坑法

int Partition1(vector<int>& v, int left, int right){
     int key = v[right];
     int end = right;
     while (left<right){
         while (left < right && v[left] < key)
              ++left;
         if (left < right)
              v[right--] = v[left];
         while (left<right && v[right]>key)
              --right;
         if (left < right)
              v[left++] = v[right];
     }
     v[left] = key;
     return left;
}
void QuickSort1(vector<int>& v, int left, int right){
     if (left<right){
         int pivotpos = Partition1(v, left, right);
         QuickSort(v, left, pivotpos - 1);
         QuickSort(v, pivotpos + 1, right);
     }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

http://blog.csdn.net/qq_34312386/article/details/60958554

归并排序

void merge(vector<int>& v,vector<int>& _v,int left,int right){
     if ( right<=left)
         return;
     int mid = left + ((right - left) >> 1);
     int left1 = left, right1 = mid, left2 = mid + 1, right2 = right;
     merge(v,_v, left1,right1 );
     merge(v, _v,left2, right2);
     int index = left;
     while (left1 <= right1 && left2 <= right2){
         if (v[left1]<v[left2])
              _v[index++] = v[left1++];
         else
              _v[index++] = v[left2++];
     }

     while (left1<=right1){
         _v[index++] = v[left1++];
     }
     while (left2<=right2){
         _v[index++] = v[left2++];
     }
     for (int i = 0; i <= right; i++)
         v[i] = _v[i];
}
void merge_sort(vector<int>& v){
     vector<int> _v(v.size());
     merge(v,_v,0,v.size()-1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

http://blog.csdn.net/qq_34312386/article/details/61721677

比较

应用场景

排序算法的选择：

1. 若n较小时，直接插入排序或选择排序，当记录规模较小时，直接插入排序较为好；否则选择排序。
2. 若基本有序，则应选用直接插入、冒泡或随机快速排序为宜
3. 若n较大，则应采用O(nlogn)的排序（快速排序、堆排序和归并排序）
1
2
3